Sıralama Algoritmaları [3] Insertion Sort

Barış Arıburnu
Yazılım Mühendisliği
14 Eki 2012
2 Yorum
1094 Görüntülenme

Sorting AlgorithmBir önceki yazı dizisinde ‘Bubble Sort‘ algoritmasını detaylı şekilde incelemiştik. Kaldığımız yerden sıralama algoritmalarını anlatmaya devam ediyoruz. Şimdi ki sıralama algoritmamız: Insertion Sort..

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(n2) ‘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

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.

Insertion-Sort-Animasyon

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ı

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

Sıralama algoritmalarından Insertion Sort Algoritmasını kavramaya çalıştık. Sıralama algoritmalarını kavramakta güçlük çekenler için; sevgili ev arkadaşım Burak Kutbay’ın kişisel sayfasında paylaşmış olduğu güzel videoları sizlere tekrar tekrar önermek istiyorum. Bu videolara ulaşmak için bu linki kullanabilirsiniz.

2 Yorum to “Sıralama Algoritmaları [3] Insertion Sort”

  1. BaBerk diyor ki:

    teşekkürler!

  2. evrim ergül diyor ki:

    Merhaba daha önceden bu algoritmayı araştırmıştım çoğu kişi anlatıyor ama sadece anlatıyor sizin sitenizde gördüğüm gif bütün anlatılanları kısaca özetledi ve konuyu anladım teşekkür ederim.elinize sağlık

Bir Cevap Yazın

E-posta hesabınız yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Şu HTML etiketlerini ve özelliklerini kullanabilirsiniz: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>