Quick Sort, bir diziyi sıralamak için önce bir elemanı pivot olarak seçer, ardından diğer elemanları bu değere göre iki tarafa ayırır. Aynı işlemi oluşan küçük parçalarda tekrarlayarak diziyi sıralar; pivotun hangi konumdan seçildiği ise parçaların büyüklüğünü ve çalışma süresini etkileyebilir.
Quick Sort böl ve yönet yaklaşımını nasıl uygular?
Quick Sort, sıralama problemini daha küçük alt dizilere ayırıp bu alt dizileri aynı yöntemle çözerek böl ve yönet yaklaşımını uygular. Bunun için seçilen pivot, dizideki diğer değerleri karşılaştırmak ve diziyi ayırmak için kullanılan elemandır.
Bölme ya da İngilizce adıyla partition, elemanları pivot değerine göre farklı taraflara yerleştirme işlemidir. Örneğin küçük veya eşit değerlerin sola, büyük değerlerin sağa alındığı bir bölmede pivot iki tarafın arasına yerleştirilir.
[7, 2, 9, 4, 3, 8] dizisinde son eleman olan 8 pivot seçildiğinde, bu kurala göre yapılan bir bölmenin ardından dizi şu duruma gelebilir:
[7, 2, 4, 3, 8, 9]Pivotun solundaki değerlerin hepsi 8'den küçük, sağındaki 9 ise 8'den büyüktür. Sol taraf henüz kendi içinde sıralı değildir; ancak 8, son sıralı dizide bulunacağı konuma yerleşmiştir.
Algoritma, pivotun sol ve sağ taraflarında aynı bölme işlemini sürdürür. Bir fonksiyonun daha küçük bir problem için kendisini çağırmasına özyineleme denir. Alt diziler sıralandığında, elemanlar dizinin içinde doğru sıraya ulaşır.
Merge Sort, ayrı ayrı sıraladığı parçaları birleştirme adımıyla bir araya getirir. Quick Sort'un burada anlatılan yerinde uygulamasında ise pivot ve alt diziler aynı dizi üzerinde düzenlenir; sonunda ayrıca birleştirme işlemi yapılmaz.
Pivot seçimi bölme sonucunu nasıl etkiler?
Pivot seçimi, bölme sonrasında oluşan alt dizilerin büyüklüğünü etkiler. Pivot değeri sıralanacak elemanları birbirine yakın büyüklükte iki parçaya ayırırsa özyinelemeli çağrılar daha dengeli ilerler. Pivot en küçük ya da en büyük değere yakınsa parçalardan biri diğerinden çok daha büyük olabilir.
| Seçim | Pivotun seçildiği konum | Dengeli bölme ihtimali | Düzenli girdilerde risk |
|---|---|---|---|
| İlk eleman | İşlenen alt dizinin başı | İlk değerin diğerlerine göre sırasına bağlıdır. | Sıralı veya ters sıralı dizide uç değer seçilir ve bölme dengesizleşir. |
| Son eleman | İşlenen alt dizinin sonu | Son değerin diğerlerine göre sırasına bağlıdır. | Sıralı veya ters sıralı dizide uç değer seçilir ve bölme dengesizleşir. |
| Ortadaki eleman | İşlenen alt dizinin orta konumu | Orta konumdaki değerin diğerlerine göre sırasına bağlıdır. | Sıralı dizide dengeli olabilir; başka düzenlerde orta konumdaki değer uç değer olabilir. |
| Rastgele eleman | İşlenen alt diziden rastgele seçilen bir konum | Seçilen değere bağlıdır; dengeli bölme kesin değildir. | Belirli bir konuma bağlı düzenli girdilerin etkisini azaltabilir, ancak dengesiz seçimler yine mümkündür. |
Ortadaki elemanı seçerken bakılan şey konumdur. Bu eleman, alt dizideki değerler sıralandığında ortada bulunacak değer olmak zorunda değildir. Birden fazla adayın değerini karşılaştırarak medyan seçen yaklaşımlar ise farklı kurallarla çalışır.
Doğru uygulanan bir Quick Sort'ta pivot seçimi, değerlerin küçükten büyüğe sıralanması sonucunu değiştirmez. Bununla birlikte, alt dizilerin dengesi değişebileceği için gereken işlem sayısı ve çalışma süresi değişebilir. Eşit değerlerin nasıl dağıtıldığı da kullanılan bölme kuralına bağlıdır.
Lomuto bölmesi örnekte hangi adımlardan geçer?
Lomuto partition yöntemi, dizinin son elemanını pivot seçerek küçük değerleri pivotun solunda toplamaya çalışır. Pivot, karşılaştırma tamamlandığında kendisinden küçük değerlerle büyük değerleri ayıran kesin konumuna yerleştirilir.
Örnekte 0 tabanlı indis kullanıyoruz. i değişkeni, pivot değerinden küçük veya eşit olan elemanların yerleşeceği sınırı gösterir. j ise diziyi soldan sağa tarayan ilerleyen sınırdır. Başlangıç dizisi şöyledir:
Başlangıç: [7, 2, 9, 4, 3, 8]
Son eleman olan 8 pivot seçilir. i değeri başlangıçta -1 olur. j sırasıyla ilk beş elemanı kontrol eder. 7, 2, 4 ve 3 pivot değerinden küçük olduğu için uygun bölgeye alınır. 9 küçük olmadığı için bulunduğu yerde bekler. Bu sırada gerekli değiş tokuşlarla dizi önce [7, 2, 4, 9, 3, 8], ardından [7, 2, 4, 3, 9, 8] hâline gelir.
Tarama bittiğinde i, pivotun yerleşmesi gereken konumun bir önceki indisindedir. Bu nedenle pivot, i + 1 konumundaki elemanla değiştirilir. Böylece 8, kendisinden küçük değerlerin hemen sağına yerleşir.
8 pivotundan sonra: [7, 2, 4, 3, 8, 9]
İlk partition işlemi sonrasında pivotun indisi 4 olur. Bundan sonra 8 yeniden karşılaştırmaya alınmaz. Yalnızca solundaki [7, 2, 4, 3] alt dizisi ve sağındaki [9] alt dizisi değerlendirilir. Tek elemanlı [9] alt dizisi için yeni bir partition işlemi gerekmez.
Sol alt dizide son eleman olan 3 pivot seçilir. 7 pivot değerinden büyük olduğu için bekler. 2 küçük olduğu için ilerleyen sınırın bulunduğu konuma taşınır ve dizi [2, 7, 4, 3, 8, 9] hâline gelir. 4 büyük olduğu için yerinde kalır. Tarama bitince 3, i + 1 konumundaki 7 ile değiştirilir.
3 pivotundan sonra: [2, 3, 4, 7, 8, 9]
Bu işlemde 3 değeri kendi kesin konumuna, yani 1 indisinin bulunduğu yere yerleşir. Solunda [2], sağında ise [4, 7] alt dizisi kalır. [4, 7] için son eleman olan 7 pivot alınır. 4 küçük olduğu için zaten doğru tarafta bulunduğundan ek bir değiş tokuş gerekmez.
7 pivotundan sonra: [2, 3, 4, 7, 8, 9]
Özyineleme hangi sınırlarla durur?
Özyineleme, partition sonrasında pivotun solundaki ve sağındaki alt diziler için aynı sıralama işleminin yeniden çağrılmasıdır. Bu çağrılarda low ve high sınırları kapsayıcı kabul edilir; yani her iki sınır da üzerinde çalışılan alt diziye dâhildir.
Pivotun indisi pivot_index ise sol alt dizi low ile pivot_index - 1 arasında, sağ alt dizi ise pivot_index + 1 ile high arasında işlenir. Pivot kendi doğru konumuna yerleştiği için bu iki çağrının hiçbirine yeniden dâhil edilmez.
Durma koşulu low >= high ifadesidir. Alt dizide tek eleman varsa low == high olur ve sıralama gerekmez. Alt dizi boşsa low > high durumu oluşur; işlem yine durur.
- Pivotu kesin konumuna yerleştirmeden alt çağrıları başlatma.
- Sol çağrıda üst sınırı
pivot_index - 1, sağ çağrıda alt sınırıpivot_index + 1olarak kullan. - Pivotu yeni alt problem aralıklarına tekrar katma.
- Tek elemanlı ve boş alt dizilerde
low >= highkoşulunun çalıştığını kontrol et.
Bu sınırları takip etmek, özyinelemeli algoritmalarda hangi parçanın işlendiğini zihinsel olarak izlemeyi kolaylaştırır. Konuyu kısa bir uygulamayla pekiştirmek için ücretsiz algoritmik düşünme testi kullanılabilir.
Quick Sort karmaşıklığı ve kararlılığı nasıl değerlendirilir?
Quick Sort'un çalışma süresi, partition işleminin diziyi ne kadar dengeli böldüğüne bağlıdır. Bir partition çağrısında seçilen aralık baştan sona taranır ve elemanlar pivot ile karşılaştırılır. Bu nedenle tek bir bölme adımı, işlenen aralığın uzunluğu açısından doğrusal çalışma gerektirir.
Bölmeler yaklaşık dengeli olduğunda dizi her özyineleme düzeyinde daha küçük parçalara ayrılır. Her düzeyde toplamda yaklaşık n eleman incelendiği ve benzer düzeylerin sayısı log n olduğu için ortalama çalışma süresi O(n log n) düzeyindedir. Big O gösterimi, girdi büyüklüğü arttıkça çalışma süresinin hangi büyüme eğilimini izlediğini anlatır.
En kötü durumda pivot, her partition sonrasında parçaların birinde n - 1 elemana yakın, diğerinde ise 0 elemana yakın bölüm bırakır. Böyle bir yapı özyineleme derinliğini artırır ve toplam çalışma süresi O(n²) seviyesine çıkabilir. İlk veya son elemanın pivot seçildiği uygulamalarda zaten sıralı ya da ters sıralı diziler bu duruma örnek oluşturabilir. Sorunun kaynağı dizinin sıralı olması tek başına değildir; pivot seçme stratejisinin bu girdide sürekli dengesiz bölünme üretmesidir.
Quick Sort kararlı bir sıralama algoritması değildir. Anahtar değerleri eşit olan iki eleman, partition sırasında yer değiştirebilir ve sıralama tamamlandığında başlangıçtaki göreli sıralarını korumayabilir. Elemanların yalnızca değerini değil, başlangıç sırasını da korumak gerekiyorsa kararlılık özelliği ayrıca değerlendirilmelidir.
Quick Sort, böl ve yönet yaklaşımıyla pivot çevresinde bölümler oluşturur; Merge Sort, parçaları ayrı ayrı sıralayıp birleştirme adımını kullanır; Bubble Sort ise komşu elemanları karşılaştırarak gerektiğinde yer değiştirir. Bu yapısal farklar, algoritmaların bellek kullanımı, pratik performansı ve farklı veri kümelerindeki davranışları üzerinde etkili olur.
Python ile yerinde Quick Sort nasıl yazılır?
Yerinde Quick Sort, sıralama işlemini aynı liste üzerinde swap yaparak gerçekleştirir. Aşağıdaki uygulamada Lomuto partition yöntemi kullanılır ve pivot olarak her aralığın son elemanı seçilir.
def partition(items, low, high):
pivot = items[high]
i = low - 1
for j in range(low, high):
if items[j] <= pivot:
i += 1
items[i], items[j] = items[j], items[i]
items[i + 1], items[high] = items[high], items[i + 1]
return i + 1
def quick_sort(items, low, high):
if low < high:
pivot_index = partition(items, low, high)
quick_sort(items, low, pivot_index - 1)
quick_sort(items, pivot_index + 1, high)
numbers = [7, 2, 9, 4, 3, 8]
quick_sort(numbers, 0, len(numbers) - 1)
print(numbers)Başlangıç çağrısında low ilk indeks olan 0, high ise son indeks olan len(items) - 1 değeridir. partition fonksiyonu pivotu uygun konumuna yerleştirir ve bu konumun indeksini döndürür. Ana Quick Sort fonksiyonu, pivotun solundaki ve sağındaki aralıkları ayrı özyinelemeli çağrılarla işler.
Bu örnekte 8 son eleman olduğu için ilk pivot olarak seçilir. Döngü sırasında pivot değerinden küçük veya ona eşit elemanlar sol bölüme taşınır. Partition tamamlandığında pivot kendi konumuna yerleşir ve sonraki çağrılar yalnızca pivotun iki tarafındaki aralıklarla devam eder.
Listenin değiştirilmesi, Python listelerinin değiştirilebilir yapıda olması sayesinde mümkün olur. Fonksiyon yeni bir sıralı liste oluşturmak yerine mevcut listenin indekslerindeki değerleri yer değiştirir. Bu nedenle fonksiyonun dönüş değerinden çok, çağrı sonrasında aynı liste nesnesinin içeriği incelenir.
[2, 3, 4, 7, 8, 9]Sınır koşullarında low < high kontrolü özyinelemeyi durdurur. Boş bir listede başlangıçta high değeri -1 olur ve fonksiyon doğrudan sona erer. Tek elemanlı listede low ile high eşit olduğu için partition çağrılmaz. Zaten sıralı bir liste de aynı algoritma akışıyla işlenir; yalnızca pivot seçiminin bölmeleri ne kadar dengeli oluşturduğu çalışma süresini etkiler.
Sık Sorulan Sorular
Quick Sort neden bazı dizilerde O(n²) çalışma süresine ulaşır?
Quick Sort, pivot seçimleri her seferinde çok dengesiz bölümler oluşturduğunda O(n²) çalışma süresine ulaşır. Bir tarafta n - 1 elemana yakın değer kalırken diğer tarafta çok az eleman kalırsa özyineleme derinleşir ve her adımda uzun bir aralığın yeniden taranması gerekir.
Lomuto partition yönteminde pivot ne zaman doğru konumuna yerleşir?
Lomuto partition yönteminde pivot, aralıktaki pivot değerinden küçük veya ona eşit elemanlar sol tarafa taşındıktan sonra doğru konumuna yerleşir. Döngü tamamlandığında pivot, solundaki elemanlardan büyük veya onlara eşit, sağındaki elemanlardan ise küçük olacak biçimde iki bölümün arasına yerleştirilir.
Quick Sort kararlı bir sıralama algoritması mıdır?
Quick Sort kararlı bir sıralama algoritması değildir. Eşit anahtar değerine sahip elemanlar partition sırasında yer değiştirebildiği için başlangıçtaki göreli sıralarını korumayabilir.
Python ile yazılan yerinde Quick Sort fonksiyonu neden yeni bir liste döndürmek yerine mevcut listeyi değiştirir?
Yerinde Quick Sort, elemanları aynı liste içindeki indekslerde değiştirerek sıraladığı için yeni bir liste oluşturmaz. Bu yaklaşımda fonksiyona verilen listenin içeriği doğrudan güncellenir ve sıralanmış sonuç çağrı sonrasında aynı liste üzerinden okunur.
Quick Sort'u değerlendirirken pivot seçimini, partition sonrasında oluşan bölümlerin dengesini, özyineleme sınırlarını ve eşit elemanların sırasını birlikte incelemek gerekir.
