Araya Sokma (Insertion Sort) Algoritması

Insertion sort algoritması temel sıralama algoritmalarından bir tanesidir. Algoritmanın mantığına göre elimizdeki A dizisinin elemanları arasında sıralama yapılmak istenildiğinde A[1] indisinden başlanarak önceki elemanlar ile karşılaştırma yapılır. Eğer A[1] indisli eleman kendinden önceki elemanlardan küçük ise yer değiştirme işlemi gerçekleşir ve dizinin başına A[1] elemanı geçer, aksi takdirde yer değiştirme işlemi gerçekleşmez ve bir sonraki elemana bakılır.

Araya sokma algoritması, sıralı bir diziye eleman ekleme işlemi için uygun bir algoritmadır. Bunun için daha çok bağlı liste (linked list) kullanılır. Eleman eklemek için karmaşıklık O(n) iken, sıralama yapmak için karmaşıklığımız O(n^2) olur.

Bir örnek ile algoritmanın çalışma mantığını gösterelim:

A dizisinin elemanları = [3, 4, 1, 8, 2, 21] şeklinde verilmiş olsun.

1.  Adım: A[1] elemanı = 4′ tür. Bir önceki eleman olan 3 ile karşılaştırıldığı zaman 3 < 4 tür ve ilk iki eleman küçükten büyüğe sıralı olduğu için bir işlem yapmamız gerekmez. 
2.  Adım: Dizinin yeni hali A [] = [3, 4, 1, 8, 2, 21] şeklindedir. A[2] = 1 dir ve 1 den önceki elemanlar 4′ ten küçüktür. O zaman 1 elamanı dizinin başına gelir ve 4 ve 3 elemanları birer sağa kaydırılır. Swap değil kaydırma işlemi uygulanır.
3. Adım: Dizinin güncel hali A[] = [1, 3, 4, 8, 2, 21] şekline gelir. Devam edelim,A [3] = 8 ‘dir.  8′ in solundaki elemanlar 8’ den küçük olduğu için kaydırma işlemi gerçekleştirilmez. İndisinimizi +1 artırarak bir sonraki elemana geçelim.
4.  Adım: A[4] = 2’dir. 2 < 8, 2 < 4, 2 < 3 olduğu için 2 elemanı dizinin A[1] indisine gelir ve diğer elemanlar birer tane sağa kaydırılır. Böylelikle dizinin güncel hali A[]= [1, 2, 3, 4, 8, 21] şeklini almış olur.
5. Adım: A[5] = 21’dir. 21 elemanı kendisinden önceki bütün elemanlardan büyük olduğu için herhangi bir indise sokma işlemi veya diğerleri arasında bir kaydırma işlemi gerçekleştirilmez. Böylelikle dizimiz küçükten büyüğe doğru sıralanmış olur. 

• Algoritmaya ait kaba kod:

arayaSokma(int A[], int N){
  int i, k , ekle;
  for(i=1; i<N; i++){
    ekle = A[i];
    
    for( k=i-1; k>=0 && ekle<=A; k--)
      A[k+1] = A[k];
    A[k+1] ekle;
  }
}  

C Kodu:

#include <stdio.h>
//global 
int A[100];
int key;
void insertionSort(int A[], int elemanSayisi){
  int i,j;
  for (i=0;i<elemanSayisi;i++){
    key = A[i];
    j = i - 1 ; //Key değerinin solu sıralı olacaktır.

    //kaydırma işlemi başlıyor
    while (key < A[j] && j >=0) {
    A[j+1] = A[j]; //birer tane kaydı
    j--;
    }
  A[j+1] = key; //araya sokma işlemi
  }
}

int main(){
  int i, adet;
  printf("\nDizi kac elemanli?\n");
  scanf("%d", &adet);
	
  for(i=0; i<adet; i++){
    printf("\n%d. sayiyi giriniz: ",i+1);
    scanf("%d", &A[i]);
  }

  insertionSort(A,adet);
	
  for(i=0; i<adet; i++){
    printf(" %d ", A[i]);
  }
	
  return 0;	
}