क्विकसर्ट एक विभाजन-र-विजय सर्ट हो जसले पिभट छान्छ, तत्वहरूलाई यससँग सानो र ठूलो गरी विभाजन गर्छ, र त्यसपछि प्रत्येक पक्षलाई पुनरावर्ती रूपमा सर्ट गर्छ। औसत 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²) सबैभन्दा खराब केस एक यादृच्छिक वा median-of-three पिभटसँग परिहार गरिन्छ। यो स्थिर छैन।
क्विकसर्ट धेरै मानक लाइब्रेरीहरूमा पूर्वनिर्धारित छ किनभने यसको उत्कृष्ट औसत-केस गति र कम मेमोरी प्रयोग।
पिभट छनोटले O(n²) सबैभन्दा खराब केस किन गर्छ भन्ने कुरा बुझ्नुले एक मुख्य पाठ सिखाउँछ: औसत र सबैभन्दा खराब केस तीव्रतापूर्वक फरक हुन सक्छ।
यो साक्षात्कार विषय एक पसंदीदा छ ठीक त्यो सूक्ष्मताको कारण।