Insertion sort(eklemeli sıralama)

Insertion sort, eleman kümesinin (array/dizi) 2. elemanından başlayarak kendinden önceki elemanlarla karşılaştırma yapar. Karşılaştırma yaptığı elemanlar kendinden büyükse bu elemanlar, küme içerisinde sağa doğru kaydırılır. Ve seçili eleman uygun yere yerleştirilir.

Insertion sort algoritmasında şüphesiz ki göze çarpan ilk olumsuz taraf, elemanların kaydırılması ile kaybedilen süre olacaktır. Daha açık biçimde özetlersek; eleman kümesinin son elemanı eğer en küçük değerse, kümenin en başına gelecek ve bütün elemanlar kaydırılacak.

En kötü durum performansı (worst-case performance) O(n²) ‘dir. En iyi durum performansı (best-case performance) O(n) ‘dir. En kötü durum performansından yola çıkarak algoritmayı değerlendirmek istersek, küçük değerler (N<1000) için sorun yaşamayacağımızı görüyoruz. Değerler büyüdükçe bizler için yükü de olumsuz yönde artıyor.

Insertion sort algoritmasının Türkçe karşılığı kaynaklarda ‘Eklemeli Sıralama Algoritması‘ olarak belirtilmiştir. Farklı kaynaklardan araştırma yapmak isteyen arkadaşlara kolaylık olsun.

Insertion sort algoritmasını gösteren görsel animasyonu incelediğimizde elemanların küme içerisinde kaydırılmasını görebilirsiniz. Böylece çalışma prensibi hakkında da ön izlenim sahibi olacağınızı düşünüyorum. Insertion sort algoritmasının dizi içerisinde sıralanmayı nasıl yaptığını ise sayılar değerler üzerinden aşağıdaki animasyonda görebilirsiniz.

Sıralama algoritmaları için uygulama yapmadan geçmiyoruz bildiğiniz gibi. Şimdi bir uygulama da insertion sort algoritması için yapalım. Not: Kopyala/Yapıştır yapmadan kendiniz yazmaya çalışırsanız daha sağlıklı olur.

C# Console Uygulaması

1 2 3 4 5 6 7 8 9 10

int[] Dizi = new int[] { 6, 5, 3, 1, 8, 7, 2, 4 }; int gecici; int onceki; for (int j = 1; j < Dizi.Length; j++) {    gecici = Dizi[j];    onceki = j - 1;    while (onceki >= 0 && Dizi[onceki] > gecici)    {       Dizi[onceki + 1] = Dizi[onceki];       onceki--;    }    Dizi[onceki + 1] = gecici; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <cstdlib> #include <iostream> using namespace std; //fonkyonların tanımlanması void insertion_sort(int arr[], int length); void print_array(int array[],int size); int main() { int array[5]= {5,4,3,2,1}; insertion_sort(array,5);  return 0; }//main bitişi void insertion_sort(int arr[], int length) {  int i, j ,tmp;  for (i = 1; i < length; i++) {  j = i;  while (j > 0 && arr[j - 1] > arr[j]) {  tmp = arr[j];  arr[j] = arr[j - 1];  arr[j - 1] = tmp;  j--;  }  print_array(arr,5);  }  }//insertion_sort bitişi. void print_array(int array[], int size){  cout<< "sıralama: ";  int j;  for (j=0; j<size;j++)  for (j=0; j<size;j++)  cout <<" "<< array[j];  cout << endl;  }//dizi yazdırma

Program Output

1 2 3 4

insertion sort adımlar: 4 5 3 2 1 insertion sort adımlar: 3 4 5 2 1 insertion sort adımlar: 2 3 4 5 1 insertion sort adımlar: 1 2 3 4 5

Sıralama algoritmalarından Insertion Sort Algoritmasını kavramaya çalıştık. Sıralama algoritmalarını kavramakta güçlük çekenler için;