Quick sort भी merge sort की तरह एक divide & conquer अल्गोरिथम पर आधारित सॉर्टिंग तकनीक है। इसे 1960 में Tony Hoare द्वारा विकसित किया गया था। इस सॉर्टिंग तकनीक में arrays के elements को दो छोटे arrays में विभाजित किया जाता है। quick sort जो है वह InPlace सॉर्टिंग का एक प्रकार है।
इस सॉर्टिंग में, सबसे पहले लिस्ट में से किसी भी element को select किया जाता है जिसे हम pivot कहते है। pivot से छोटे elements इसके बाएं तरफ रहेंगें। जबकि pivot से बड़े elements इसके दायीं तरफ रहेंगे।
Quick sort की औसत complexity:- O (n log n) है। तथा इसकी worst case complexity:- O (n^2) है जहाँ n, elements की संख्या है । क्योंकि worst case में भी quick sort की complexity कम होती है इसलिए यह बहुत तेज तथा efficient है।
Quick Sort Algorithm
इस सॉर्टिंग की algorithm निम्नलिखित है।
step1. Array लिस्ट में एक element को select करते है जिसे हम pivot वैल्यू कहते है।
step 2. Elements को इस प्रकार दूबारा arrange करते है कि वे सभी elements जो pivot वैल्यू से छोटी है वे arrays के बायीं तरफ रहती है और वे सभी elements जो pivot वैल्यू से बड़ी होती है उन्हें array के दायीं तरफ रखा जाता है। और वह element जो pivot के सामान होते है उन्हें array में किसी भी तरफ रखा जा सकता है।
step 3. Array के दोनों भागों को सॉर्ट किया जाता है। दोनों भागों को दुबारा quick sort algorithm का प्रयोग करके सॉर्ट किया जाता है।
Quick sort example:-
