Recursive quick sort

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.

Ö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 = [5, 2, 8, 1, 9]
quick_sort(arr, 0, 4)
print(arr)

Kendini test et

Recursive quick sort: kavramları eşleştir

Temel durum

lo >= hi
Pivot

Ortada kalır
Sol

Küçükler
Sağ

Büyükler
Quick sort yerinde midir?
- Hayır, ek dizi gerekir
- Sadece iyi pivot ile
- Sadece küçük dizilerde
- Evet, sadece takas
Cevabı göster

Evet, sadece takas — Evet, sadece takas
Temel durum
```
if lo ____hi:
```
Cevabı göster
```
if lo >=hi:
```

Sıradaki ders: Özet - Quick sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler