Recursive quick sort
- Algoritmalar kursu
- Orta seviye
- Ders 7/80
- 4 dk
Her iki tarafı recursive olarak sıralamayı ve O(n log n) ortalamayı öğrenirsin.
Recursive quick sort
Quick sort, partition sonrası pivot'un solundaki ve sağındaki alt dizileri recursion ile sıralar. Pivot artık doğru konumundadır, bir daha hareket etmez.
Temel durum: alt dizi tek elemanlıysa (lo >= hi) sıralı sayılır. Her çağrı bir partition + iki recursive çağrı yapar.
İyi pivot ile her seviye yarıya indirir; derinlik log n, toplam O(n log n). Kötü pivot O(n^2).
Yerinde sıralama
Quick sort yerinde (in-place) çalışır: ek dizi oluşturmaz, sadece takaslarla diziyi düzenler. Bellek O(log n) (recursion yığını).
Bu, merge sort'un O(n) ek belleğine göre bir avantajdır. Ama kararlı değildir: eşit elemanların sırası bozulabilir.
Pratikte küçük alt dizilerde (ör. 10 eleman altı) insertion sort'a geçilir; bu performansı artırır.
Uygulama Recursive quick sort
quick_sort(arr, lo, hi) yaz. lo >= hi ise dön; değilse partition yap, iki tarafı recursion ile sırala. arr=[5,2,8,1,9]; quick_sort(arr,0,4); print(arr) ile [1, 2, 5, 8, 9] yazdır.
Başlangıç kodu
def quick_sort(arr, lo, hi):
# Böl ve recursion ile sıralaÖrnek çözüm
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
def quick_sort(arr, lo, hi):
# Böl ve recursion ile sırala
if lo >= hi:
return
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
arr = [5, 2, 8, 1, 9]
quick_sort(arr, 0, 4)
print(arr)Beklenen çıktı
[1, 2, 5, 8, 9]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Recursive quick sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Temel durum |
lo >= hi |
Pivot |
Ortada kalır |
Sol |
Küçükler |
Sağ |
Büyükler |
2 Quick sort yerinde midir?
- Hayır, ek dizi gerekir
- Sadece iyi pivot ile
- Sadece küçük dizilerde
- Evet, sadece takas Doğru cevap
Açıklama: Evet, sadece takas
3 Temel durum
if lo ____hi:if lo >=hi:Açıklama: >= doğru.