Ekleme sıralamanın analizi

Seçmeli sıralama gibi, ekleme sıralama dizenin indeksleri üzerinde döngüler. $1,2,3,\dots ,n-1$‍ indekslerindeki ögelerde insert çağırır. indexOfMinimum a her çağrı gibi, inserte her çağrının süresi de sıralanmış alt dizinin uzunluğuna bağlıdır. Aslında, bir önceki cümlede ''bağlıdır'' yerine, ''bağlı olabilir'' de diyebilirdik, bunun nedenini göreceğiz.

insert ü çağırdığımız ve bir alt diziye eklenen değerin, bu alt dizideki ögelerin hepsinden daha küçük olduğu bir durumu düşünelim. Örneğin, eğer [2, 3, 5, 7, 11] alt dizisine 0 ekliyorsak, bu durumda alt dizideki her öge bir konum sağa kaymalıdır. Buna göre, genel olarak, eğer $k$‍ ögeli bir alt diziye ekleme yapıyorsak, tüm $k$‍ bir konum sağa kaymak zorunda olabilir. Bir ögeyi bir anahtarla karşılaştırmak ve ögeyi kaydırmak için tam olarak kaç kod satırına ihtiyacımız olduğunu saymak yerine, bunun sabit bir satır sayısı olduğuna mutabık olalım ve bunu $c$‍ sabiti olarak adlandıralım. Buna göre, $k$‍ ögeli bir alt diziye ekleme yapmak için $c\cdot k$‍ satıra kadar gerek duyabiliriz.

inserte her çağrıda, eklenen değerin dizide solundaki her ögeden daha küçük olduğunu varsayın. Birinci kere insert çağırdığımızda, $k=1$‍'dir. İkinci seferde, $k=2$‍'dir. Üçüncü seferde,$k=3$‍'tür. Böylece, son seferde $k=n-1$‍ olur. Böylece, sıralanmış alt dizelere eklemek için harcanan toplam süre,

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

Bu toplam bir aritmetik seridir, yalnızca $n-1$‍ 'e gider, $n$‍'ye değil. Aritmetik seri formülümüzü kullandığımızda, alt dizilere eklemek için harcanan toplam sürenin şu olduğunu buluruz:

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

Büyük-θ gösterimini kullanırsak, alt dereceden terim $cn/2$‍ ile $c$‍ ve 1/2 sabit faktörlerini çıkardığımızda, bu durumda ekleme sıralamanın çalışma süresinin $\mathrm{\Theta }(n^2)$‍ olduğunu buluruz.

Ekleme sıralama $\mathrm{\Theta }(n^2)$‍ kezden daha az sürebilir mi? Cevap, evettir. [2, 3, 5, 7, 11] dizisini düşünün, burada sıralanmış alt dizi ilk dört ögedir ve biz 11 değerini ekliyoruz. İlk testte 11'in 7'den büyük olduğunu buluruz, dolayısıyla alt dizideki ögelerden hiç birisinin sağa kaymasına gerek yoktur. O zaman, bu insert çağrısı sabit zaman alır. Her insert çağrısının sabit zaman aldığını varsayalım. inserte $n-1$‍ çağrı olduğundan, eğer her çağrı sabit süre ($c$‍) alıyorsa, bu durumda ekleme sıralama için toplam süre $c\cdot (n-1)$‍'dir; bu $\mathrm{\Theta }(n^2)$‍ değil, $\mathrm{\Theta }(n)$‍'dir.

Bu durumlardan biri oluşabilir mi? insert e her çağrı alt dizideki her ögenin bir konum sağa kaymasına neden olabilir mi? insert'e yapılan her çağrı hiçbir ögenin kaymamasına yol açabilir mi? İki sorunun da cevabı evettir. Eğer eklenen anahtar solundaki ögelerin tümünden küçükse, insert e her çağrı her ögenin kaymasına neden olur. Buna göre, eğer her öge solundaki her ögeden küçükse, ekleme sıralamanın çalışma zamanı $\mathrm{\Theta }(n^2)$‍'dir. Her ögenin solundaki ögeden küçük olması ne anlama gelir? Dizinin ters sırada, [11, 7, 5, 3, 2] gibi başlaması gerekir. Dolayısıyla, ekleme sıralama için en kötüsü, ters sıralanmış bir dizidir.

Bu durumun tersi nedir? Eğer eklenen anahtar solundaki ögelerin tümünden büyük veya eşitse, insert e yapılan bir çağrı hiç bir ögenin kaymasına yol açmaz. Buna göre, her öge solundaki ögeden büyük veya eşitse, ekleme sıralamanın çalışma zamanı $\mathrm{\Theta }(n)$‍'dir. Bu durum, dizi zaten sıralanmış olarak başladığında olur ve dolayısıyla zaten sıralanmış olan bir dizi, ekleme sıralama için en iyi durumdur.

Ekleme sıralamanın çalışma zamanı için başka neler söyleyebiliriz? Diyelim ki, dize rastgele bir sırayla başlar. Bu durumda, ortalamada, her bir ögenin solundaki ögelerin yarısından az olmasını beklerdik. Bu durumda, ortalamada, $k$‍ ögelik bir alt dizide bir insert çağrısı, bunların $k/2$‍'sini kaydırır. Çalışma zamanı, en kötü durumdaki çalışma zamanının yarısı olur. Ancak sabit katsayıların önemli olmadığı asimptotik gösterimde, ortalama durumda çalışma süresi (aynı en kötü durum gibi)$\mathrm{\Theta }(n^2)$‍ olacaktır.

Eğer dizinin ''neredeyse sıralanmış'' olduğunu bilseydiniz ne olurdu, yani her öge, sıralandığında olması beklenen, en fazla sabit konum sayısından -diyelim ki 17- başlasaydı? Bu durumda insert e her çağrı en fazla 17 ögeyi kaydırır ve $k$‍ ögelik bir dizideki bir insert çağrısı için süre maksimum $17\cdot c$‍ olacaktır. insert e $n-1$‍ çağrının tamamında, çalışma süresi $17\cdot c\cdot (n-1)$‍ olacaktır, bu en iyi durumda olduğu gibi $\mathrm{\Theta }(n)$‍'dir. Neredeyse-sıralanmış bir dizi verildiğinde, ekleme sıralaması hızlı olur.

Özetlersek, ekleme sıralama için çalışma zamanları:

Ekleme sıralamanın tüm durumlarına uygun bir genel bir ifadede bulunmamız gerekseydi, $O(n^2)$‍ zamanında çalıştığını söylememiz gerekirdi. Bunun her durumda $\mathrm{\Theta }(n^2)$‍ zamanda çalıştığını söyleyemezsiniz, zira en iyi durum $\mathrm{\Theta }(n)$‍ zamanda çalışır. Bunun her durumda $\mathrm{\Theta }(n)$‍ zamanda çalıştığını da söyleyemezsiniz, zira en kötü durumda çalışma zamanı $\mathrm{\Theta }(n^2)$‍'dir.

Bu içerik Dartmouth Bilgisayar Bilimleri öğretim görevlileri Thomas Cormen ve Devin Balkcom ile Khan Academy bilgisayar bölümü içeriklerini hazırlayan takımın işbirliği ile hazırlanmıştır. İçerik CC-BY-NC-SA lisanslıdır.