Bölme işlemi
- Algoritmalar kursu
- Orta seviye
- Ders 6/80
- 4 dk
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.
Başlangıç kodu
def partition(arr, lo, hi):
# Lomuto bölmesiÖrnek çözüm
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))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Yer değiştirme
arr[i], arr[j] = arr[j], ____arr[i], arr[j] = arr[j], arr[i]Açıklama: arr[i] doğru.
2 Bölme işlemi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
i işaretçisi |
Küçük sınırı |
Pivot |
Son eleman |
Takas |
Yer değiştir |
Dönüş |
Pivot konumu |
3 Bölme adımı kaç iş yapar?
- O(1)
- O(log n)
- O(n) Doğru cevap
- O(n^2)
Açıklama: O(n)