Eklemeli sıralama

Eklemeli sıralama, çoğu insanın elindeki kartları dizme yöntemidir: sıradaki kartı alır, zaten sıralı olan kartların arasında doğru yere yerleştirirsiniz. Uzun rastgele listelerde yavaştır, ancak kısa veya neredeyse sıralı listelerde çok hızlıdır; bu yüzden gerçek sıralama kütüphaneleri onu hâlâ kullanır.

Sıralanan çubuklar: solda sıralı bir kısım ve daha büyük çubukları geçerek bu kısma geri kayan bir çubuk
Sıralanan çubuklar: solda sıralı bir kısım ve daha büyük çubukları geçerek bu kısma geri kayan bir çubuk

Fikir

Listenin başını sıralı tutun. Başta bu sıralı kısım yalnızca ilk değerdir. Sıradaki değeri alın ve kendinden önceki değerle karşılaştırın. Önceki daha büyükse yerlerini değiştirin ve bir sıra daha geride yeniden karşılaştırın. Önceki değer daha büyük olmadığında ya da değer en başa ulaştığında durun. Sıralı kısım bir değer büyümüştür. Sona kadar her değerle bunu tekrarlayın.

Bir örnek

5, 1, 4, 2, 8 listesini alalım. 1. geçiş 1'i alır: 5 daha büyük, yer değiştirirler ve 1 en başa ulaşır: 1, 5, 4, 2, 8. 2. geçiş 4'ü alır: 5 ile yer değiştirir, sonra 1'de durur: 1, 4, 5, 2, 8. 3. geçiş 2'yi alır: 5 ve 4 ile yer değiştirir, sonra 1'de durur: 1, 2, 4, 5, 8. 4. geçiş 8'i alır; 8 zaten 5'ten büyük olduğu için tek karşılaştırma yeter. Toplam 7 karşılaştırma ve 4 takas. Kabarcık sıralaması aynı listede 9, seçmeli sıralama 10 karşılaştırma yapar.

Takas sayısı tersinme sayısına eşittir

Tersinme, yanlış sırada duran bir değer çiftidir. Sırası yanlış iki komşuyu takas etmek tam olarak bir tersinmeyi ortadan kaldırır ve eklemeli sıralama yalnızca böyle komşuları takas eder. Yani başlangıç listesinde kaç tersinme varsa tam o kadar takas yapar; kabarcık sıralamasıyla aynı sayıda. Her geçiş ayrıca takasa yol açmayan en fazla bir karşılaştırma yapar: geçişi durduran karşılaştırma. Dolayısıyla karşılaştırma sayısı, tersinme sayısı artı en fazla n − 1'dir.

Uyarlanabilir: liste neredeyse sıralıyken hızlı

İş miktarı tersinme sayısı artı yaklaşık n olduğu için eklemeli sıralama, tersinme az olduğunda hızlıdır. Sıralı bir liste n − 1 karşılaştırma gerektirir ve hiç takas gerektirmez. Her değerin doğru yerinden yalnızca birkaç sıra uzakta olduğu bir liste n'ye yakın sürede biter. Yalnızca sıralı olmaktan çok uzak bir liste, örneğin n(n − 1)/2 tersinmeli ters sıralı bir liste, n² ile orantılı süre alır. Rastgele bir listede ortalama yaklaşık n²/4 takas yapılır.

Nerede kullanılır

Eklemeli sıralama kararlıdır, ek bellek gerektirmez ve ek yükü çok azdır. Kısa listelerde, kâğıt üzerinde daha hızlı olan algoritmaları geçer. Python ve Java'daki Timsort ve C++'ta kullanılan introsort gibi birçok kütüphane sıralaması, listenin küçük parçaları için, genellikle birkaç düzine değere kadar, eklemeli sıralamaya geçer. Değerlerin tek tek geldiği veriler için de uygundur, çünkü her yeni değer gelir gelmez yerine eklenebilir.

Kendiniz keşfedin

Uygulamayı açın ve Oynat'a basın ya da her seferinde bir karşılaştırma ilerlemek için Adım'a basın. Eklenen değerin kendi rengi vardır, karşılaştırıldığı değer vurgulanır ve sıralı kısım yeşildir. Kabarcık sıralaması ve seçmeli sıralamadan farklı olarak yeşil kısım kesin değildir: daha sonra gelen daha küçük bir değer hâlâ içine kayabilir. Geçişlerin ne kadar kısa olduğunu görmek için neredeyse sıralı bir liste, ardından ters sıralı bir liste deneyin.

Sık sorulan sorular

Eklemeli sıralamanın zaman karmaşıklığı nedir?

En kötü ve ortalama durumda O(n²), en iyi durumda, yani zaten sıralı bir listede O(n). Daha kesin söylemek gerekirse süre, n artı tersinme sayısıyla orantılıdır. Yalnızca O(1) ek bellek gerektirir.

Eklemeli sıralama ile seçmeli sıralama arasındaki fark nedir?

Seçmeli sıralama en küçük değeri bulmak için sıralanmamış kısmın tamamını tarar; bu yüzden her zaman n(n − 1)/2 karşılaştırma yapar ama az takas yapar. Eklemeli sıralama sıradaki değeri geldiği gibi alır ve yalnızca gerektiği kadar geri taşır; bu yüzden özellikle neredeyse sıralı listelerde daha az karşılaştırma, ama daha fazla takas yapar.

İkili eklemeli sıralama nedir?

Yeni değerin yerini sıralı kısımda ikili aramayla bulan bir sürüm. Bu, en fazla n yerine yaklaşık log n karşılaştırma gerektirir. Ancak yer açmak için değerlerin yine kaydırılması gerekir; bu yüzden taşıma sayısı ve en kötü durumdaki O(n²) aynı kalır.

Eklemeli sıralama kararlı mıdır?

Evet. Bir değer yalnızca kesinlikle daha büyük olan değerleri geçerek geri gider; bu yüzden eşit değerler ilk sıralarını korur.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Eklemeli sıralamayı deneyin