Quick Sort भी Merge Sort की तरह एक Divide & Conquer Algorithm पर आधारित Sorting Technique है,
इसे 1960 में Tony Hoare द्वारा विकसित किया गया था ।
इस Sorting में, सबसे पहले List में से किसी भी Element को Select किया जाता है जिसे हम Pivot कहते है Pivot से छोटे Elements इसके Left तरफ रहेंगें, जबकि Pivot से बड़े Elements इसके Right तरफ रहेगें।
Quick Sort Algorithm
- Step 1 :- सबसे पहले Array List में एक Element को Select करते है जिसे हम Pivot वैल्यू कहते है ।
- Step 2 :- Elements को इस प्रकार दूबारा Arrange करते है कि वे सभी Elements जो Pivot Value से छोटी है वे Arrays के बायीं तरफ(Left Side) रहती है और वे सभी Elements जो Pivot Value से बड़ी होती है उन्हें Array के दायीं तरफ (Right Side) रखा जाता है, और वह Element जो Pivot के सामान होते है उन्हें Array में किसी भी तरफ रखा जा सकता है ।
- Step 3 :- Array के दोनों भागों को Sort किया जाता है, दोनों भागों को दुबारा Quick Sort Algorithm का प्रयोग करके Sort किया जाता है ।
Quick Sort Example
मान लिजिए हमारे पास निम्नलिखित Array है जिसे कि हमे Sort करना है।
सबसे पहले Array List में एक Element को Select करते है जिसे हम Pivot वैल्यू कहते है । वैसे आप किसी भी Element को Pivot मान सकते है लेकिन मै इस Array के सबसे अन्तिम Element 8 को Pivot मान रहा हूँ ।
अब हम Pivot Element की सभी Elements से तुलना करते है जो Element, Pivot Element से छोटा होगा उसे Pivot के Left side रखते है और जो Pivot से बड़ा होगा उसे Right रखते है।
इस प्रकार हमारा Array 3 भागों में विभाजित हो जाता है 8 और 9 Elements Array में Single Element है इसलिए यह Sorted है क्योंकि इसमें केवल एक ही Element है और जिस Array में एक Element होता है वह Sorted Array ही होता है। फिर हम Pivot Element के Left Side के Array को Sort करेगें
इसे भी हम उसी प्रकार Sort करेगें जैसे पहले हमने किया था हम अपने Array के अन्तिम Element को Pivot मान लेगें और फिर Pivot Element की सभी Elements से तुलना करते है जो Element, Pivot Element से छोटा होगा उसे Pivot के Left side रखते है यहां पर Pivot Element से छोटा कोई Element नहीं है और फिर जो Pivot से बड़ा होगा उसे Right रखते है।
इस प्रकार हमारा Array पुनः दो भागों में विभाजित हो जाता है पहला Array में केवल एक Element है इसलिए ये तो Sorted ही है । अगले Array को हम पुनः इसी Process से Sort करेंगे ।
पुनः हम वही करेगें जो हम ऊपर करते आ रहे है Array के अन्तिम Element को Pivot Element मान लेगें और फिर Pivot Element की सभी Elements से तुलना करते है जो Element, Pivot Element से छोटा होगा उसे Pivot के Left side रखते है और Pivot से बड़ा होगा उसे Right रखते है।
इस प्रकार हमारा Array का प्रत्येक Element, Single Element में विभाजित हो जाता है और Single Element Array एक Sort Array होता है क्योंकि उसको हम किसी से Compare नहीं कर सकते है इसलिए वह हमेशा Sorted ही होता है।
और इन सभी Single Element Array को क्रमबद्ध आपस में Collect कर लेते है और हमें एक Sorted Array प्राप्त हो जाता है।
निवेदक – : आश करता हूं आपके यह पोस्ट पसन्द आयी हो अगर आप भी हमें अपनी कुछ विचार हमारे साथ साझा करना चाहते है जिससे मैं और अच्छे से पोस्ट लिख सके या आप इसी प्रकार से अन्य टॉपिक को समझना चाहते है तो हमें आप कृपया कमेन्ट बॉक्स में जरूर बताए क्योंकि आपका ये प्रयास हमें आगे बढ़ने में मदद करेगा ।