Bölme işlemi

Pivottan küçükleri sola, büyükleri sağa dizmeyi öğrenirsin.

Bölme işlemi

Bölme (partition), pivot'tan küçükleri sola, büyükleri sağa toplar. Tek geçişte, O(n) işle yapılır.

Klasik Lomuto yöntemi: bir i işaretçisi küçüklerin sınırını tutar. Her eleman pivot ile karşılaştırılır; küçükse i ilerletilir ve yer değiştirilir.

Sonunda pivot i+1 konumuna yerleştirilir; sol taraf küçükler, sağ taraf büyükler olur. Pivot artık doğru yerindedir.

Lomuto yöntemi

Lomuto yöntemi kolay anlaşılır ama Hoare yönteminden daha çok takas yapar. i = lo - 1 ile başlanır, her küçük elemanda i += 1 yapılıp takas edilir.

Geçiş bitince pivot i+1 ile takas edilir; dönüş değeri i+1 olur (pivot'un yeni konumu).

Bu konum, recursion'da sol ve sağ alt dizilerin sınırını belirler.

Uygulama Bölme — Lomuto

partition(arr, lo, hi) yaz. arr[hi] pivot. Küçükleri sola topla, pivot'u yerine koy, indeksi döndür. arr=[4,2,7,1,5]; print(partition(arr,0,4)) ile 3 yazdır.

Örnek çözümü göster

def partition(arr, lo, hi):
    # Lomuto bölmesi
    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
arr = [4, 2, 7, 1, 5]
print(partition(arr, 0, 4))

Kendini test et

Yer değiştirme

arr[i], arr[j] = arr[j], ____

Cevabı göster

arr[i], arr[j] = arr[j], arr[i]

Bölme işlemi: kavramları eşleştir

i işaretçisi

Küçük sınırı
Pivot

Son eleman
Takas

Yer değiştir
Dönüş

Pivot konumu
Bölme adımı kaç iş yapar?
- O(1)
- O(log n)
- O(n)
- O(n^2)
Cevabı göster

O(n) — O(n)

Sıradaki ders: Recursive quick sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler