Hızlı sıralama
Hızlı sıralama (quicksort) en çok kullanılan sıralama algoritmalarından biridir. Bir pivot seçer, listeyi pivottan küçük değerler ve geri kalanlar olarak ikiye ayırır, sonra iki tarafı da aynı şekilde sıralar. Pratikte hızlıdır ve ek bir listeye ihtiyaç duymaz, ama ne kadar hızlı olduğu pivota bağlıdır.
Temel fikir
Bir değeri pivot olarak seçin. Listeyi, pivottan küçük her değer onun önüne, diğer her değer arkasına gelecek şekilde yeniden düzenleyin. Bu düzenlemeye bölümleme denir ve pivotu sıralı listede tam ait olduğu yere bırakır. İki taraf artık birbirinden bağımsız problemlerdir: her birini hızlı sıralamayla sıralayın. Tek değerli ya da boş bir taraf zaten sıralıdır.
Adım adım bölümleme
Uygulama Lomuto bölümlemesini kullanır. Pivot kısmın sonuna taşınır. Bir işaretçi baştan başlar: onun önündeki her şey pivottan küçüktür. Diğer her değer pivotla karşılaştırılır; daha küçükse işaretçinin yerine takas edilir ve işaretçi bir yer ilerler. Sonunda pivot işaretçinin yerine takas edilir. Son değer pivot olmak üzere 5, 1, 4, 2, 8 listesini alalım: dört değerin hepsi 8'den küçüktür, bu yüzden 8 sonda kalır. 5, 1, 4, 2 kısmı 2 etrafında bölümlenir ve 1, 2, 4, 5 elde edilir; 4, 5 ise 5 etrafında bölümlenir. Toplam 8 karşılaştırma, 2 takas ve 3 bölümleme.
İyi ve kötü pivotlar
Her pivot ortaya düşseydi her bölümleme problemi yarıya indirir ve sıralama yaklaşık n log₂ n karşılaştırma gerektirirdi. Rastgele bir listede pivotlar nadiren mükemmeldir ama genellikle yeterince iyidir: 40 rastgele değer için uygulama yaklaşık 190 karşılaştırma sayar. En kötü durum, pivot her seferinde en küçük ya da en büyük değer olduğunda ortaya çıkar. Pivot olarak son değer seçilirse zaten sıralı ya da ters bir listede tam olarak bu olur: her bölümleme yalnızca pivotu ayırır ve sıralama n(n − 1)/2 karşılaştırma gerektirir; 40 değer için 780.
Pivotu seçmek
Rastgele bir pivot, hiçbir özel sıra onu kandıramayacağı için en kötü durumu her girdi için son derece olasılık dışı kılar. Üçün medyanı, yani ilk, orta ve son elemandan ortanca olanı, ucuzdur ve sıralı ve ters listelerle iyi başa çıkar. İkisini de uygulamada sıralı bir listede deneyin; karşılaştırmalar 780'den yaklaşık 150'ye düşer. Çok sayıda eşit değer başka bir sorundur: hepsi pivotun aynı tarafına düşer. Pivota eşit değerleri ortadaki bir kısımda tutan üç yollu bölümleme bunu çözer.
Tarihçe ve kullanım
Tony Hoare hızlı sıralamayı 1959'da buldu ve 1961'de yayımladı. Kendi bölümlemesi listeyi iki uçtan tarar ve daha az takas yapar; burada gösterilen daha basit Lomuto sürümü ders kitapları sayesinde yaygınlaştı. Hızlı sıralama yerinde sıralar ve iç döngüsü çok kısadır; bu yüzden kararlı olmasa da pratikte genellikle birleştirme sıralamasından hızlıdır. C++ standart kütüphanesindeki sıralama olan introsort, hızlı sıralamayı çalıştırır ve bölümlemeler fazla dengesizleşirse yığın sıralamasına geçer; böylece en kötü durumu n log n kalır.
Kendiniz keşfedin
Uygulamayı açın ve Adım'a basın. Bölümlenen kısım gölgelidir, pivotun kendi rengi vardır ve kesikli çizgi sol kısmın, yani pivottan küçük değerlerin sonunu gösterir. Her pivot son yerine ulaştığında yeşile döner. Sıralı bir liste ve pivot olarak son değeri seçin, sonra üçün medyanına geçin ve sayaçları karşılaştırın.
Sık sorulan sorular
Hızlı sıralamanın zaman karmaşıklığı nedir?
Ortalamada ve iyi pivotlarla O(n log n), en kötü durumda O(n²). Yerinde sıralar; küçük taraf önce sıralanırsa özyineleme O(log n) ek bellek gerektirir.
Lomuto ve Hoare bölümlemesi arasındaki fark nedir?
Lomuto tek bir işaretçi tutar ve soldan sağa tarar; bu kolay izlenir ve bu uygulamanın gösterdiği de budur. Hoare iki uçtan birbirine doğru tarar ve yanlış tarafta duran çiftleri takas eder; bu da ortalamada yaklaşık üç kat daha az takas demektir.
Çok sayıda değer eşitken hızlı sıralama neden yavaştır?
Pivota eşit değerlerin hepsi aynı tarafa gider; bu yüzden az farklı değer içeren bir liste dengesiz bölünür, tamamen eşit değerlerden oluşan bir liste ise en kötü durum kadar kötüdür. Pivota eşit değerleri ortada toplayan üç yollu bölümleme bunu önler.
Hızlı sıralama kararlı mı?
Hayır. Bölümleme sırasındaki takaslar değerleri uzak mesafelere taşır, bu yüzden eşit değerlerin sırası değişebilir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Hızlı sıralamayı deneyin