Özet - Quick sort

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.

Örnek çözümü göster

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)

Kendini test et

Özet - Quick sort: kavramları eşleştir

Pivot

Bölme ekseni
Bölme

O(n)
Ortalama

O(n log n)
Kötü durum

O(n^2)
Bellek maliyeti
```
Ek bellek: O(____)
```
Cevabı göster
```
Ek bellek: O(log n)
```
Quick sort kararlı mıdır?
- Hayır
- Sadece küçük dizilerde
- Sadece iyi pivot ile
- Evet, her zaman
Cevabı göster

Hayır — Hayır

Sıradaki ders: Heap nedir?

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler