Seçmeli sıralama
Kalan en küçük değeri bulur ve onu bir sonraki konumdaki değerle yer değiştirir. Çok az yer değiştirme yapar, ama karşılaştırma sayısı hep aynıdır.
- en iyi Ω(n²)
- ortalama Θ(n²)
- en kötü O(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
- şimdiki en küçük
- 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. Karşılaştırma sayısı, diğer tüm listelerdekiyle tam olarak aynıdır.
Nasıl çalışır
Sıralanmamış kısımda en küçük değer aranır. Bu değer, sıralanmamış ilk değerle yer değiştirir ve böylece bir değer daha son yerine oturur. Liste zaten sıralı olsa bile kalan her değer yine de kontrol edilir.
Ne zaman iyi bir seçimdir
Veriyi taşımak pahalı ama okumak ucuzsa işe yarar, çünkü her konum için en fazla bir kez yer değiştirir. Diğer çoğu durumda eklemeli sıralama daha iyi bir basit seçimdir.