1. Araya Sokma Sıralaması (Insertıon Sort)

Diyelim ki elimizde bir sayı dizisi olsun : 33 44 21 83 56 73 22

O ana kadarki sıralı kısma  ‘ I ‘ koyalım.

İlk geçişte : ilk sayıdan bahsettiğimiz için ( 33 ) kendi başına sıralıdır. Hiç bir işlem yapmadan devam eder.

33  I   44  21  83  56  73  22

ikinci geçişte : 44 ile gerisindekileri kıyaslar 44 33ten büyüktür. Herhangi bir değişiklik yapılmaz.

33   44  I  21  83  56  73  22

üçüncü geçişte : 21 ile gerisindekileri kıyaslar 21 44ten küçüktür. 21 ile 44ü yer değiştirir yani swap yapar. Daha sonra tekrar 21 ile 33 ü kıyaslar 21 33ten de küçüktür. 21 ile 33ü yer değiştirir yani swap yapar.

33   44  I  21  83  56  73  22    –>   33  21  44  I  83  56  73  22   –>  21  33  44  I  83  56  73  22

dördüncü geçişte : gelen sayımız 44ten büyük olduğundan bir değişiklik yapımaz

21  33  44  83  I   56  73  22

beşinci geçişte : 56 83ten küçük. 56 ve 83 swap edilir. Daha sonra 56 ile 44 kıyaslanır. 56 44ten küçük değil bir değişiklik yapılmaz.

21  33  44  83  I   56  73  22 –>  21  33  44  56  83  I   73  22

altıncı geçişte :

21  33  44  56  83  I   73  22 –>   21  33  44  56  73  83  I    22

yedinci geçişte :

21  33  44  56  73  83  I    22  –>  21  33  44  56  73  22  83 I  –>  21  33  44  56   22  73   83 I   –>    21  33   44   22  56  73   83 I   –>  21  33    22  44  56 73   83 I  –>   21  22  33  44  56 73   83 I

INSERTION SORT ALGORITMA ANALIZI

Worst case : TAM TERS VERİLMİŞ DİZİ  [n*(n+1)]/2   :  n^2
Best case : TAM SIRALI DİZİ   n tane sayinin üzerinden birer defa geçeceğinden : n
Kıyas : Selection sorta göre best casede avantajlı worst casede aynı.


INSERTION SORT  C# KODU

   public void insertion_sort(int[] dizi) 
   {
     for(int j = 1; j < dizi.Length; j++)
     {
        int key = dizi[j]; //her dönüşte dizinin kendinden önceki elemanlarla kıyaslanacak elemanını key'de tutar.
        int i = j - 1;  //bu elemanın bir gerisinde yer alan elemanın index'ini de i'de tutar.
        while (i >= 0 && dizi[i] > key) //eğer eleman bir gerisindekinden küçükse while çalışır.
        {
          dizi[i + 1] = dizi[i];  //büyük eleman bir sonraki index'e yani aslinda j'ye itilir.
           i = i - 1;  //bu kontrol her seferinde bir gerisindeki için devam eder bu da i azaltılarak yapılır.
        }
        dizi[i + 1] = key;
      }
    }
     /*Insertion Sort Kullanımı*/
    int[] dizi = { 12, 3, 8, 5, 15, 12, 45, 31 };
    insertion_sort(dizi);