Quicksort, bir pivot seçen, elemanları bundan daha küçük ve daha büyük olanlara bölen, ardından her bir tarafı özyinelemeli olarak sıralayan böl-ve-fethet bir sıralama algoritmasıdır. Ortalama O(n log n), en kötü durum O(n²).
Bölümlendirme, pivot'u nihai sıralanmış konumuna yerleştirir; solundaki her şey daha küçük, sağındaki her şey daha büyük. Her iki tarafta özyinelemeli olarak çalışı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]
(Uygulamada belleği tasarrufu sağlamak için yerinde bölümlendirme kullanılır.)
| Durum | Zaman | Neden |
|---|---|---|
| Best/Average | O(n log n) | dengeli bölümler |
| Worst | O(n²) | kötü pivot ile zaten sıralanmış |
Yerinde quicksort O(log n) yığın alanı kullanır.
Genellikle uygulamada en hızlısıdır önbellek dostu ve düşük ek yükü nedeniyle ve yerinde olmasıdır. Rastgele veya üçün medyanı pivot ile O(n²) en kötü durum kaçınılır. Stabil değildir.
Quicksort, harika ortalama durum hızı ve düşük bellek kullanımı nedeniyle birçok standart kütüphanede varsayılandır.
Pivot seçiminin neden O(n²) en kötü durumuna yol açtığını anlamak önemli bir dersi öğretir: ortalama ve en kötü durumlar keskin bir şekilde farklılık gösterebilir.
Söyleşi konusu olarak tercih edilir çünkü tam olarak bu incelik yüzündendir.