Pivot seçimi
- Algoritmalar kursu
- Orta seviye
- Ders 5/80
- 4 dk
Quick sort'ta pivot elemanı seçip diziyi bölmeyi öğrenirsin.
Pivot seçimi
Quick sort, bir pivot eleman seçip diziyi pivot'tan küçükler ve büyükler olarak ikiye ayırır. Pivot seçimi performansı belirler.
İlk, son veya orta eleman sık seçimlerdir. Kötü pivot (en küçük veya en büyük) her adımda sadece bir eleman ayırır; bu durumda maliyet O(n^2) olur.
Rastgele pivot veya üç-ortanca stratejisi kötü durum riskini azaltır. İyi pivotta ortalama O(n log n) çalışır.
Pivot stratejileri
İlk eleman seçimi, zaten sıralı bir dizide felaket olur: her adımda bir eleman ayrılır. Son eleman da aynı riski taşır.
Üç-ortanca: ilk, orta ve son elemanların ortancasını pivot alır. Sıralı ve ters sıralı dizilerde iyileşme sağlar.
Rastgele: uniform rastgele seçim kötü durum olasılığını düşürür. Pratikte çok etkilidir.
Uygulama Pivot seç ve yazdır
pick_pivot(arr) yaz. Son elemanı pivot olarak seç ve döndür. print(pick_pivot([3, 1, 4, 1, 5, 9])) ile 9 yazdır.
Başlangıç kodu
def pick_pivot(arr):
# Son elemanı pivot alÖrnek çözüm
def pick_pivot(arr):
# Son elemanı pivot al
return arr[-1]
print(pick_pivot([3, 1, 4, 1, 5, 9]))Beklenen çıktı
9
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kötü pivot hangi maliyeti verir?
- O(1)
- O(n^2) Doğru cevap
- O(log n)
- O(n)
Açıklama: O(n^2)
2 Pivot seçimi
pivot = arr[____]pivot = arr[-1]Açıklama: -1 doğru.
3 Pivot seçimi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
İlk pivot |
Riskli |
Rastgele |
Güvenli |
Üç-ortanca |
Dengeli |
Kötü durum |
O(n^2) |