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

INSERTION SORT ALGORITMASI

Insertion sort(Araya sokma sıralaması) algoritmasında problemimiz verilen sırasız bir diziyi sıralamak üzerine kurulu. Algoritma her seferinde dizinin üzerinde ileri doğru ilerleyerek, dizinin bir elemanını alıp geriye doğru elemanlar ile bir bir sıralar ve her bir sıralamasında, eğer sıraladığı elemandan daha küçükse o elemanla yer değiştirerek bir geriye atar.

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 gerisindeki sayı olan 33’ü 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 bir gerisindeki sayıyı 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.

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 yapmaz.

21  33  44  83  I   56  73  22

beşinci geçişte : 56 83ten küçüktür dolayısıyla 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

Bu şekilde sırasız bir dizi sıralı hale gelir.

INSERTION SORT ALGORITMA ANALIZI

Worst case : TAM TERS VERİLMİŞ DİZİ, bu durumda dizinin her bir elemanı bir gerisindekinden küçük olacaktır. Dolayısıyla 1inci eleman için iç döngü 0 2 eleman için geriye doğru 1, 3. eleman için iki daha sonra 3 4 5 6… n kadar geriye hareket yapacaktır. Yani 0+1+2+3+4…..+n-1 = [n*(n-1)]/2   :  n^2
Best case : TAM SIRALI DİZİ,   n tane sayinin üzerinden birer defa geçer ve hiç birini geriye doğru ilerletme gereği olmadığı için bu tek geçişle kalır. Yani n
Avarage case :
Worst case ile best casein ortalamasını aldığımızda   n^2 olarak buluruz.

INSERTION SORT  C# KODU

Aslında yukarıdaki algoritma stepleri bize kodun yapısı hakkında ip ucu veriyor. Bir index dizi üzerinde her seferinde bir ileri gidip yeni elemanı tutacakken bir index de her seferinde bu yeni elemanı alıp gerisindeki rakamlar ile kıyaslayacak. Dolayısıyla dizi üzerinde bir ileri doğru ilerleyen bir de geriye doğru giden iki index olmalı. Yani iç içe iki adet döngü kullanmamız gerekir. Bu da aslında yukarıda da bahsettiğimiz gibi n üzeri 2 gibi bir complexitiye karşılık gelir.

   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);