C Programlama İnsertion Sort Algoritması

İnsertion Sort Nedir?

Türkçe ismi Ekleme Sıralaması olan İnsertion Sort algoritması diğer sıralama algoritmalarına nazaran kodlaması oldukça kolaydır. Kodlanması kolay olduğu gibi uygulanması da kolaydır. Genelde kart oyunlarında insanlar elindeki kartları sıralamak için farkında olmadan bu algoritmayı uygulamaktadır. Ancak karmaşıklığı N^2 olduğu için verimli bir algoritma sayılmaz.

İnsertion Sort Nasıl Çalışır?

Algoritmada döngümüz her bir tur döndüğünde sıradaki elemanı sondan başa doğru karşılaştırarak yerine yerleştirme esaslı çalışmaktadır.

Az önce de dediğim gibi üstteki for döngüsü her bittiğinde dizideki i. elemanı yani ‘deger‘ değişkeni doğru yerini bulmuştur. Doğru derken kastettiğim 0 ile i arasındaki doğru yerini bulmuştur. Döngü en sona geldiğinde 0 dan n-1 e kadar herkes doğru yerini bulduğu için dizi sıralanmıştır.

Hemen bir örnek vererek daha rahat kavramaya çalışalım.

for (i = 1; i < n; i++)
   {
       deger = arr[i];
       j = i-1;
 
       while (j >= 0 && arr[j] > deger)
       {
           arr[j+1] = arr[j];
           j--;
       }
       arr[j+1] = deger;
   }

Not: ‘[‘ ve ‘]’ ayraçlarıyla ayrılmış kısım halihazırda sıralanmış aralığı temsil eder.

Başlangıç

[10] 3 9 2 1

1. Adım

[3 10] 9 2 1

2. Adım

[3 9 10] 2 1

3. Adım

[2 3 9 10] 1

4. Adım

[1 2 3 9 10]

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int main()
{
 int dizi[5]={24,5,63,4,3};
 int i,j,mevcut;
 for(i=1;i<5;i++)
 {
  mevcut=dizi[i];
  j=i;
  while(j>0 && dizi[j-1]>mevcut)
  {
   dizi[j]=dizi[j-1];
   j--;
  }
  dizi[j]=mevcut;
  
 }
 for(i=0;i<5;i++)
 {
 printf("%d\t",dizi[i]);
 }
 
 system("pause");
 return 0;
 }
 //İnsertion sortde araya eklme olaya vardır 0 dan buyuk ve diizini yanındakı elmanınakadar ust uste yazar en sıonunda sabit yerine yazmaktadır.
 //insertion sortde kaydırma yapılmaktdır.
/* for(i=1;i<n;i++)
 {
  mevcut=dizi[i];
  j=i;
  while(j>0 && dizi[j-1]>mevcut)
  {
   dizi[j]=dizi[j-1];
   j--;
  }
  dizi[j]=mevcut;
 }
}*/