Eklemeli sıralama
Solda, her seferinde bir değer ekleyerek sıralı bir kısım oluşturur. Her yeni değer dışarı alınır ve kendinden küçük bir değere varana kadar sola taşınır.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- evet
- evet
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
- dışarı alınan
- sıralı kısım
- son yerinde
Şunu deneyin: Neredeyse sıralı bir liste seçin. Neredeyse hiçbir değer kaymaz, bu yüzden çok az adımda biter.
Nasıl çalışır
Sol kısım her zaman sıralıdır. Sıradaki değer dışarı alınır, sıralı kısımdaki her büyük değer bir konum sağa kaydırılır ve değer açılan boşluğa konur. Birçok kişi elindeki iskambil kâğıtlarını böyle sıralar.
Ne zaman iyi bir seçimdir
Kısa listeler ve neredeyse sıralı listeler için iyi bir seçimdir, bunlarda çok hızlıdır. Gerçek sıralama kütüphaneleri de daha hızlı yöntemlerin içinde listenin küçük parçaları için onu kullanır.