Pivot seçimi

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.

Örnek çözümü göster

def pick_pivot(arr):
    # Son elemanı pivot al
    return arr[-1]
print(pick_pivot([3, 1, 4, 1, 5, 9]))

Kendini test et

Kötü pivot hangi maliyeti verir?
- O(1)
- O(n^2)
- O(log n)
- O(n)
Cevabı göster

O(n^2) — O(n^2)
Pivot seçimi
```
pivot = arr[____]
```
Cevabı göster
```
pivot = arr[-1]
```
Pivot seçimi: kavramları eşleştir

İlk pivot

Riskli
Rastgele

Güvenli
Üç-ortanca

Dengeli
Kötü durum

O(n^2)

Sıradaki ders: Bölme işlemi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler