EKLEYEREK SIRALAMA(INSERTION SORT)

Sıralama algoritmalarının içerisinde yer alan Insertion Sort yani ekleyerek sıralama algoritmasının iki farklı metodu bulunmaktadır.Anlatımımı algoritmanın iki ozelliği ile ayrı ayrı betimleyeceğim.Bir Array’a elemanlar atanırken önce büyüklük-küçüklük durumuna göre bakılır.Eklenecek sayı,dizide bulunan elemanlardan büyük bir sayı ise sorun yoktur ve dizinin boş indeksine eklenir.Fakat eklenecek sayı dizideki herhangi bir sayıdan küçük ise,ekleneceği konumdan itibaren listedeki sayılar 1’er sıra kaydırılacaktır ki ekleyeceğimiz sayıya yer açılmış olsun.Bir örnekle konumuzu anlatmaya devam edelim.Aynı veri türlerinden oluşacak ve içi boş olan bir kümemiz olsun.Şimdi bu kümemize elemanlar ekleyelim.

Örneğin,ilk olarak 7 sayısını ekliyoruz.

7 - - - -. -> 7 sayısı listemizde oluşturuldu.

Daha sonra 5 sayısını eklemek istediğimizi varsayalım.Ekleme yapılmadan önce eklenecek sayı ile listedeki elemanlar karşılaştırılacaktır.Listemizde şuan sadece 7 sayısı bulunduğundan yalnızca 1 sefer tarama yapılacaktır.Ekleyeceğimiz 5 sayısı 7 sayısından küçük olduğu için listemizde bulunan 7 sayısı bir kayarak 5 sayısına yer açmış olur.Dolayısıyla 5 sayısı yeni yerine yerleşecektir.

5 7 - - -

Eklemeye yeni sayımız 8 ile devam ediyoruz.8 sayısı önce 5 ile test edecektir. 5<8 olduğu için,sıra 7’ye gelir.7<8 olduğu için ve başka test edecek sayı olmadığı için 8 sayısı listedeki ilk boş yere yerini alacaktır.Yeni durumda görünüm,

5 7 8 - - olacaktır.

Şimdi ise 6 sayısını eklemeye çalışalım.Dikkat edilirse 6 sayısı arada kalacak bir sayıdır ve 5’ten büyük fakat 7’den küçük bir sayıdır.O yüzden 5’ten sonraki tüm sayılar 1’er sıra kaydırılır.

5 – 7 8 - ancak 6 sayısına bu şekilde yer açılabilir,yeni durumda görünüm,

5 6 7 8 - olacaktır.

Son olarak 2 sayısını ekleyeceğimizi düşünelim.2 sayısı,listedeki ilk eleman olan 5 sayısı ile test edilecektir.2<5 olduğu için 2 sayısının yeri belirlenmiş olup, artık diğer elemanlarla test edilmesine gerek kalmaz.Çünkü 2 sayısı diğer elemanlardan zaten küçük olacaktır ve bakmak gereksizdir. Dolayısıyla listedeki 5 sayısından itibaren tüm sayılar 1’er sıra kaydırılacaktır. Nihayi dörünüm 2 5 6 7 8 şeklinde olacaktır.

Ekleyerek sıralama algoritmasının ilk versiyonu yukarıda anlatılan mantıkla çalışır.

2.Versiyon

Algoritmanın bir de 2.versiyonu bulunmaktadır.Bu versiyon derki,dizide bir sıralı bölüm olsun bir de düzensiz bölüm olsun.Yukarıdaki örneklerde bahsi geçen sayılar tek seferde diziye yerleştirilir.Yukarıdaki örneğimizdeki elemanların ekleme sırası ile dizimize elemanları yerleştirelim.

7   5   8   6   2

5   7   8   6   2

5   7   8   6   2

5   7   6   8   2

5   6   7   8   2

5   6   7   2   8

5 6 2 7 8
5 2 6 7 8
2 5 6 7 8

Analizi yapılan algoritmanın C dilindeki karşılığı verilmiştir.

int InsertionSort(int dizi[]){
  int sayi=0,flag=0,i,j,k=0;
  dizi=(int *)malloc(boyutsizeof(int));
  printf("Boyutu 5 olan bir dizinin elemanlarını giriniz.");
  scanf("%d",&sayi);
  dizi[0]=sayi;
  for(i=1;isayi){
        for(k=i-1;k>=j;k--)
        dizi[k+1]=dizi[k];
        dizi[j]=sayi;
        flag=1;
        break;
      }
    }
    if(flag==0)
    dizi[i]=sayi;
    flag=0;
  }
  return dizi;
}

Bağlı liste modeli kullanıldığında aynı algoritma aşağıdaki gibi verilebilir.

node InsertionSort(node *kutu,int data){
  if(kutu==NULL){
    kutu=(node *)malloc(sizeof(node));
    kutu->data=data;
    kutu->next=NULL;
    return kutu;
  }
  if(datadata){
    node *temp=(node)malloc(sizeof(node));
    temp->next=kutu;
    temp->data=data;
    return temp;
  }
  node iter=kutu;
  node *root=kutu;
  while(iter->next!=NULL){
    if(iter->next->data > data){
      node *temp=(node *)malloc(sizeof(node));
      temp->data=data;
      temp->next=iter->next;
      iter->next=temp;
      return kutu;
    }
    iter=iter->next;
  }
  if(iter->NULL){
    node *temp=(node *)malloc(sizeof(node));
    temp->data=data;
    iter->next=temp;
    temp->next=NULL;
    return kutu;
  }
}

int *InsertionSort(int dizi[]){
  int sayi=0,temp=0,i,j;
  dizi=(int *)malloc(boyutsizeof(int));
  printf("Boyutu 5 olan bir dizinin elemanlarını giriniz.");
  for(i=0;i=0;j--){
      if(dizi[j+1]


şeklinde bir kod dilimi gerçeklenmiş olacaktır.

Kategori : Algoritmalar