INSERTION SORT

• Insertion_sort verilen dizideki elemanları, kendi isteğimiz doğrultusunda sıralamamıza yardımcı olur.
• Yerinde sıralama yapar.
• Eğer verilen dizi sıralı ise T(n)=Q(n) 'dir.
• Eğer verilen dizi ters sıralı ise T(n)=Q( n2 )'dir.
• Eğer verilen dizi karışık sıralı ise T(n)=Q( n2 )'dir.

_____________________________________________________

Algoritması:

insertion_sort(A)

  for j <-- 2 to length [A]

      do key <-- A[j]

         i <-- j-1

     

         while i>0  and A[i] > key

               do A [i+1] <-- A[i]

                    i <-- i-1

         A[i+1] <--key

_____________________________________________________

Bir örnek vermek gerekise, bize verilen dizi:

A[ ] ={5,2,4,6,1}  olsun. Şimdi bu algoritmaya göre bu diziyi sıralayalım. Burada dizinin ilk elemanı A[0] değil A[1] 'dir.

Burada ilk olarak,
i=1  ,  j=2  ,  key=2  olur.   ( Burada i ve j dizinin ilk iki elemanı olduğu için 1 ve 2 değerini aldı. )

for döngüsünün içindeki while döngüsüne girince karşılaştırma başlar. A[1]>key olduğu için (5>2),  A[i] ile A[i+1] yer değiştirir. Yani başlangıç kısmını düzelterek yazarsak,

A[ ]={2,5,4,6,1} olur dizinin yeni hali.

Hemen ardından,

j=3  ,  key=4  , i=2 olur.  ( Bu kısım for döngüsünün hemen altındaki while döngüsüne girmeden önce hallediliyor. )

While döngüsünde A[2] ile key karşılaştırılıyor. A[2] daha büyük olduğu için key ile (yani  A[3] ile) A[2] yer değiştirir.

Dizinin yeni hali:

A[ ] ={2,4,5,6,1] olur.

j=4  ,  key=6  , i=3 olduğunda bir değişiklik olmayacağı açıktır. (5<6 olduğu için) Dizi aynen kalır.

j=5  ,  key=1 ,  i=4   olduğunda   A[4]=6 > 1 olduğu için yer değiştirirler.

Dizinin yeni hali:


A[ ] = {2,4,5,1,6} olur. while içinde  i bir azalıyordu. O zaman i=3 olur. Key de A[4] (yani 1)  olur. while döngüsündeki şart yeniden sağlandığı için ( A[3] >  A[4] ) tekrar yer değiştirilir. Key yine 1'dir. Burada 1 en başa gelinceye kadar yer değiştirme olur. Key hep 1 olacak i de bir azalacak. Ne zaman ki while döngüsündeki şart sağlanmıyorsa o zaman bu işlem duracak. 


Döngü sonlandığında, dizinin yeni hali: A[ ] ={1,2,4,5,6} 'dir. Zaten son elemana gelindiği için for döngüsünden de çıkılır ve dizi sıralanmış olur.


____________________________________________________

En kötü durum (Worst Case) analizi :


A [i] ' yi sıralarken maksimum karşılaştırma sayısı  (i-1)'dir. Dolayısı ile karşılaştırma sayısı toplam işlem zamanını vereceğinden,

Twc(n) £  å i = 2 to n  (i -1)

              £ å j = 1 to n-1   (j) 

              = n(n-1)/2

              = Q(n2)

Buradan T(n) = Q(n2) çıkar. 


______________________________________________________

En iyi durumda zaten sıralı geleceğinden en iyi durum analizi tahmin edilebileceği gibi  T(n) = Q (n) 'dir.