Yığın sıralaması
Listeyi bir yığına dönüştürür. Yığın, her ebeveynin çocuklarından büyük olduğu bir ağaçtır. Sonra en büyük değeri tekrar tekrar sona taşır.
- en iyi Ω(n log n)
- ortalama Θ(n log n)
- en kötü O(n log n)
- bellek O(1)
- kararsız
- ek bellek istemez
Bunlar ne demek?
- En iyi durum: girdi bu algoritma için en kolay olduğunda sürenin liste boyutu n ile nasıl arttığı.
- Ortalama: sürenin n ile olağan artışı. n²'de değer sayısı iki katına çıkınca süre yaklaşık dört katına çıkar; n log n çok daha yavaş artar.
- En kötü durum: en zor girdideki artış. Hızın asla düşmemesi gerektiğinde işe yarar.
- Bellek: listenin dışında ne kadar ek bellek gerektiği. 1 birkaç değişken, n listenin bir kopyası demektir.
- Kararlı: eşit iki değer başlangıçtaki sıralarını korur. Kayıtlar tek bir alana göre sıralanırken önemlidir.
- Ek bellek istemez: ikinci bir liste olmadan, listenin kendi içinde sıralar.
- karşılaştırılıyor
- taşınıyor
- son yerinde
Oynat'a basın: çizgiler maliyetin nasıl arttığını gösterir
Oynat tuşuna basın veya algoritmada adım adım ilerleyin.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: Ters sıralı bir liste seçin. Yığın neredeyse hiç yer değiştirmeden kurulur, sonra her tur en büyük değeri sona taşır.
Nasıl çalışır
Yığın, listenin kendi içinde tutulur: i konumundaki değerin çocukları 2i+1 ve 2i+2 konumlarındadır, en büyük değer de hep en baştadır. Bu değer sondaki değerle yer değiştirir, yığın bir konum küçülür ve onarılır. Sıralı kısım sağdan büyür.
Ne zaman iyi bir seçimdir
En kötü durumda bile hızın iyi kalması ve ek bellek kullanılmaması gerektiğinde, örneğin küçük cihazlarda. Ortalamada hızlı sıralamadan yavaştır, bu yüzden çoğu zaman yedek çözüm olarak kullanılır.