Quicksort एक divide-and-conquer sort है जो एक pivot चुनता है, elements को उससे छोटे और बड़े हिस्सों में partition करता है, फिर प्रत्येक हिस्से को recursively sort करता है। औसत O(n log n), worst case O(n²)।
Partitioning, pivot को उसकी अंतिम sorted स्थिति पर रख देता है; बाईं ओर सब कुछ छोटा होता है, दाईं ओर सब कुछ बड़ा होता है। दोनों ओर recurse करें।
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(व्यवहार में memory बचाने के लिए in-place partitioning का उपयोग किया जाता है।)
| Case | Time | कारण |
|---|---|---|
| Best/Average | O(n log n) | संतुलित partitions |
| Worst | O(n²) | खराब pivot के साथ पहले से sorted |
In-place quicksort O(log n) stack space का उपयोग करता है।
यह आमतौर पर cache-friendliness और कम overhead के कारण व्यवहार में सबसे तेज़ होता है, और यह in-place भी है। O(n²) worst case को randomized या median-of-three pivot का उपयोग करके टाला जाता है। यह stable नहीं है।
Quicksort अपनी उत्कृष्ट average-case गति और कम memory उपयोग के कारण कई standard libraries में default है।
यह समझना कि pivot का चुनाव O(n²) worst case का कारण क्यों बनता है, एक मुख्य सबक सिखाता है: average और worst case में तीव्र अंतर हो सकता है।
यह interviews में एक पसंदीदा विषय ठीक इसी बारीकी के कारण है।