Yığın sıralaması
Yığın sıralaması, en büyük değeri bulmanın daha iyi bir yolunu kullanan seçmeli sıralamadır. Sıralanmamış değerleri bir yığında, yani listenin kendi içinde saklanan ve en büyük değerin hep tepede olduğu bir ağaçta tutar. O değeri alıp yığını onarmak, tüm listeyi taramak yerine yaklaşık log n adım sürer.
Liste içinde bir ağaç
İkili yığın, işaretçiye ihtiyaç duymayan bir ağaçtır. 0 konumu köktür ve i konumunun çocukları 2i + 1 ve 2i + 2 konumlarıdır; yani 1 ve 2 konumları kökün çocukları, 3 ile 6 arasındaki konumlar bir sonraki seviyedir ve bu böyle sürer. Son seviye hariç her seviye doludur, sonuncusu soldan dolar. Maksimum yığında her ebeveyn çocuklarından küçük değildir, bu yüzden en büyük değer her zaman köktedir.
Aşağı indirme
Tüm işi tek bir işlem yapar. Bir değeri aşağı indirmek için onu çocuklarıyla karşılaştırın. Büyük olan çocuk değerden büyükse yer değiştirirler ve değer yeni çocuklarıyla karşılaştırılır. Hiçbir çocuk daha büyük olmadığında ya da değer en alta ulaştığında durur. Ağacın yalnızca yaklaşık log₂ n seviyesi olduğu için bir aşağı indirme en fazla yaklaşık 2 log₂ n karşılaştırma yapar.
Önce yığını kurmak, sonra sıralamak
Yığını kurmak için sondaki ebeveynden köke doğru her ebeveyni aşağı indirin. Her alt ağaç, ebeveyni içine inmeden önce zaten bir yığındır. Sonra sıralayın: kökü, yani en büyük değeri, yığının son değeriyle takas edin. O değer artık son yerindedir. Yığın bir kısalır ve köke gelen değer yığını onarmak için aşağı iner. Tek bir değer kalana kadar tekrarlayın.
Bir örnek
5, 1, 4, 2, 8 listesini alalım. Yığın kurulurken 1, 8'in altına iner, sonra 5, 8'in altına iner; sonuç 8, 5, 4, 2, 1 olur. Şimdi 8 sona gider; 1 köke gelir ve 5 ile 2'yi geçerek aşağı iner: 5, 2, 4, 1 | 8. Sonra 5 sona gider ve 1, 4'ü geçerek aşağı iner: 4, 2, 1 | 5, 8. İki tur daha listeyi bitirir: 12 karşılaştırma ve 10 takastan sonra 1, 2, 4, 5, 8.
Güçlü ve zayıf yönleri
Yığın sıralaması en kötü durumda bile n log n ile orantılı süre alır ve ek bellek gerektirmez. Hızlı sıralama n²'ye kadar yavaşlayabilir, birleştirmeli sıralama ise liste uzunluğunda bir tampon ister; bu yüzden yığın sıralaması güvenli bir yedektir: C++ standart kütüphanesinin kullandığı introsort, hızlı sıralamanın bölmeleri kötü gittiğinde ona geçer. Gerçek bilgisayarlarda genellikle ikisinden de yavaştır, çünkü listedeki uzak yerler arasında sıçrar; ayrıca kararlı değildir. J. W. J. Williams yığın sıralamasını ikili yığınla birlikte 1964'te yayımladı.
Kendiniz keşfedin
Uygulamayı açın ve Adım'a basın. Çubukların üstündeki ağaç yığını gösterir: aşağı inen değerin kendi rengi vardır, karşılaştırıldığı çocuk vurgulanır ve her takas hem ağaçta hem çubuklarda görünür. Yığın kurulunca kökün sona taşınmasını, yeşile dönmesini ve ağaçtan çıkmasını izleyin.
Sık sorulan sorular
Yığın sıralamasının zaman karmaşıklığı nedir?
En iyi, ortalama ve en kötü durumda O(n log n). Yığını kurmak O(n), n − 1 çıkarmanın her biri O(log n) sürer. O(1) ek bellekle yerinde sıralar.
Yığın sıralaması ile seçmeli sıralama arasındaki fark nedir?
İkisi de kalan en büyük (veya en küçük) değeri tekrar tekrar alır. Seçmeli sıralama onu sıralanmamış kısmın tamamını tarayarak bulur, her seferinde n karşılaştırma. Yığın sıralaması sıralanmamış kısmı en büyük değerin zaten tepede olduğu bir yığında tutar ve yığını onarmak yalnızca yaklaşık log n karşılaştırma tutar.
Yığın, sıralama dışında ne için kullanılır?
Öncelik kuyrukları için: yığın en büyük (veya en küçük) öğeyi hemen verir ve öğe eklemeyi ya da çıkarmayı yaklaşık log n adımda yapar. Görev zamanlayıcılar, Dijkstra'nın en kısa yol algoritması ve olay simülasyonları hep yığın kullanır.
Yığın sıralaması kararlı mıdır?
Hayır. Kökü sona taşımak 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.
Yığın sıralamasını deneyin