Özet - Quick sort
- Algoritmalar kursu
- Orta seviye
- Ders 8/80
- 4 dk
Quick sort uygulayıp sonucu yazdıran mini görev yaparsın.
Özet - Quick sort
Quick sort: pivot seç, böl, recursion ile sırala. Yerinde çalışır, O(log n) ek bellek (yığın). İyi pivotta ortalama O(n log n), kötü pivotta O(n^2).
Kararlı değildir. Pratikte çok hızlıdır; küçük alt dizilerde insertion sort ile hibrit kullanılır.
Pivot seçimi performansın anahtarıdır: rastgele veya üç-ortanca güvenli seçimlerdir.
Uygulama Özet: quick sort
quick_sort(arr, lo, hi) yaz. arr=[3,1,4,1,5,9,2]; quick_sort(arr,0,6); print(arr) ile [1, 1, 2, 3, 4, 5, 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 = [3, 1, 4, 1, 5, 9, 2]
quick_sort(arr, 0, 6)
print(arr)Beklenen çıktı
[1, 1, 2, 3, 4, 5, 9]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Quick sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Pivot |
Bölme ekseni |
Bölme |
O(n) |
Ortalama |
O(n log n) |
Kötü durum |
O(n^2) |
2 Bellek maliyeti
Soru
Ek bellek: O(____)
Cevap
Ek bellek: O(log n)Açıklama: log n doğru.
3 Quick sort kararlı mıdır?
- Hayır Doğru cevap
- Sadece küçük dizilerde
- Sadece iyi pivot ile
- Evet, her zaman
Açıklama: Hayır