Quicksort هو نوع من أنواع الترتيب التي تتبع استراتيجية divide-and-conquer، حيث يختار pivot، ويقسم العناصر إلى تلك الأصغر والأكبر منه، ثم يقوم بترتيب كل جانب بشكل متكرر. متوسط الحالة O(n log n)، والحالة الأسوأ O(n²).
التقسيم يضع الـ pivot في موضعه النهائي المرتب؛ كل شيء على اليسار أصغر، وكل شيء على اليمين أكبر. قم بالعودية على كلا الجانبين.
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]
(يتم استخدام التقسيم في المكان (in-place) في الممارسة العملية لتوفير الذاكرة.)
| الحالة | الوقت | السبب |
|---|---|---|
| أفضل/متوسط | O(n log n) | تقسيمات متوازنة |
| أسوأ | O(n²) | مرتب بالفعل مع pivot سيء |
يستخدم quicksort في المكان (in-place) مساحة stack بمقدار O(log n).
عادة ما يكون الأسرع في الممارسة العملية بسبب صداقته للـ cache والحد الأدنى من الزيادة، وهو يعمل في المكان. يتم تجنب الحالة الأسوأ O(n²) باستخدام عشوائي أو median-of-three pivot. إنه غير مستقر.
Quicksort هو الافتراضي في العديد من المكتبات القياسية بسبب سرعة متوسط الحالة الممتازة واستخدام الذاكرة المنخفض.
فهم سبب تسبب اختيار الـ pivot في الحالة الأسوأ O(n²) يعلم درسًا رئيسيًا: يمكن أن تتباعد الحالة المتوسطة والحالة الأسوأ بشكل حاد.
إنه موضوع مفضل في المقابلات بالضبط بسبب هذا التفصيل الدقيق.