Quicksort एक विभाजन-आणि-जय करणे ॲल्गोरिदम आहे जो पिव्होट निवडतो, घटकांना त्यापेक्षा लहान आणि मोठ्यात विभाजित करतो, नंतर प्रत्येक बाजूला पुनरावृत्तीने सॉर्ट करतो. सरासरी O(n log n), सर्वात वाईट केस O(n²).
विभाजन पिव्होटला त्याच्या अंतिम सॉर्ट केलेल्या स्थानावर ठेवते; सर्वकाही डावीकडे लहान आहे, सर्वकाही उजवीकडे मोठे आहे. दोन्ही बाजूंना पुनरावृत्तीने विभाजित करा.
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]
(व्यवहारात मेमरी वाचवण्यासाठी इन-प्लेस विभाजन वापरले जाते.)
| केस | वेळ | कारण |
|---|---|---|
| सर्वोत्तम/सरासरी | O(n log n) | संतुलित विभाजन |
| सर्वात वाईट | O(n²) | आधीच सॉर्ट केलेले खराब पिव्होटसह |
इन-प्लेस क्विकसॉर्ट O(log n) स्टॅक स्पेस वापरते.
सामान्यतः व्यवहारात सर्वात वेगवान कॅश मैत्रीपूर्ण आणि कमी ओव्हरहेडमुळे, आणि ते इन-प्लेस आहे. O(n²) सर्वात वाईट केस यादृच्छिक किंवा मध्यम-तीन पिव्होटसह टाळली जाते. हे स्थिर नाही.
क्विकसॉर्ट हे अनेक मानक लायब्ररींमध्ये डिफॉल्ट आहे कारण त्याचा उत्तम सरासरी-केस गती आणि कमी मेमरी वापर आहे.
पिव्होट निवडीमुळे O(n²) सर्वात वाईट केस का होते हे समजून घेणे एक महत्त्वाचा धडा शिकवते: सरासरी आणि सर्वात वाईट केस तीव्रपणे भिन्न होऊ शकते.
हे अगदी तया सूक्ष्मतेमुळे मुलाखत विषय आहे.