Insertion Sort (Araya Ekleme) Algoritması

Sıralama algoritmaları makalelerine devam ediyorum ve bu makalede Insertion Sort yani araya ekleme sıralama algoritmasını anlatıyorum. Algoritma kavramı: bazı değerleri girdi olarak alan ve bazı değerleri de çıktı olarak üreten iyi tanımlanmış bir hesaplama sürecidir. Bu yüzden algoritma tanımını yaparken bu girdileri çıktılara dönüştüren bir hesaplama adımları sıralaması olduğunu söyleyebiliriz. Bir veri dizisi üzerinde sıralama işleminin yapılabilmesini sağlayan çeşitli sıralama algoritmaları vardır. Bu algoritmaların her birinin sıralama işlemini gerçekleştirme tarzı da farklılık göstermektedir. Bu yüzden zaman karmaşıklığı da algoritmalar arasında değişken olmaktadır.

Resim-1

Insertion Sort yani araya ekleme sıralama algoritması ikinci elemandan başlayarak elemanın kendinden önceki elemanlarla karşılaştırılması suretiyle büyük elemanların dizide sağa doğru kaydırılması işlemlerini tekrar eder. Böylelikle açılan yere o anda sıralanmakta olan eleman yerleşecektir. Yapılan işi toparlayacak olursak öncelikle dizideki ikinci eleman başlangıç elemanı olarak seçilir ve kendisinden önce gelen yani solunda eleman ile kıyaslanır. Eğer birinci eleman ikinci elemandan büyükse yer değiştirirler. Değilse bir sonraki elemana geçilir. İkinci eleman birinci indise alınır ilk eleman ikincisi indise alınır ve üçüncü eleman ile ikinci eleman kıyaslanır.  Bu şekilde dizi elemanlarının hepsine bakılana kadar ve doğru sıralama elde edilene kadar işlem devam eder. Bu algoritmanın örneğin kabarcık (bubble sort) sıralama algoritmasına göre güzel yanı sıralanmakta olan eleman yerleştirilirken solundaki diğer tüm elemanlar ile de kontrol edilir. Bu şekilde sağındakiler kendisinden büyükler solundakiler ise kendisinden küçükler olacak şekilde daha hızlı bir sıralama yapılmış olur. Yani her seferinde bir solundaki eleman ile kıyasa girmez. Eğer bir solundaki kendisinden küçükse direk onunla yer değişmek yerine solda kalan diğer elemanlara da bakar ve kendisine uygun olan yere girer.

Araya ekleme algoritması ile ilgili olarak şu maddeleri sıralayabiliriz.

• Karmaşıklığı O(n^2) dir.
• Küçük veri kümelerinde verimli çalışır.
• Büyük dizilerde başarısı düşük bir algoritmadır.
• Sıralanacak diziyi yerinde sıralamaktadır. Ek bir bellek alanı istemez.
• Sıralama esnasında da veriye yeni elemanlar eklenebilir.

Örnek:

20,15,5,1,9,13 dizisi sıralanacak olsun. Bu diziyi araya ekleme algoritması yardımıyla sıralamak için;

1. Dizinin ikinci elemanı başlangıç elemanı olarak seçilir.  20,15,5,1,9,13
2. Daha sonra 15 ile 20 kıyas edilir. 15 < 20 olduğu için 15 başa alınır ve 20 ikinci sıraya yerleşir. Dizinin yeni hali böyle olur: 15,20,5,1,9,13
3. Şimdi de üçüncü eleman olan 5 ile 20 kontrol edilir. 5 < 20 ancak aynı zamanda 5 < 15 olduğundan 5 sayısı en başa alınır ve sayılar sırasına göre kaydırılır. Dizinin yeni hali: 5,15,20,1,9,13 olur.
4. Bu adımda da sıra dördüncü eleman yani 1 sayısına bakmaya gelmiştir. 1 hepsinden küçük olduğu için direk sola kaya kaya en başa yerleşir ve diğer sayılarda birer sağa kayarak kendi sırasını alırlar. Dizinin son hali: 1,5,15,20,9,13 olacaktır.
5. Bu adımda sıralanmak üzere bakılacak indis değeri beştir. Yani karşılığında bulunan eleman 9’dur. 9 sayısı solundaki 20,15,5,1 ile kontrol edilir ve kendi yerine araya girerek dizinin son halini şu şekilde oluşturur: 1,5,9,15,20,13.
6. Bu adımı son adım olarak düşünebiliriz. Burada da dizinin altıncı indis değerinde bulunan eleman olan 13 kontrol edilir. 13 < 20, 13 < 15 ve 13 > 9 kontrolü yapılır ve araya girerek kendisine ait olan sırasında yerini alır. Dizinin son hali ise : 1,5,9,13,15,20 olarak sıralanmış olur.

Algoritmanın Analizi:

Algoritmanın analiz edilmesi demek bir algoritmanın çalışması için gerektirdiği kaynakların ön görülmesi demektir. Bizim burada ön görmek ve dikkat etmek istediğimiz kaynak diğer bilgisayar mühendisliği problemlerindeki gibi disk, performans gibi donanımsal değil aslında ölçmek istediğimiz şey zamandır. Bu yüzden bizler bir problemin çözümünde farklı farklı algoritmaları analiz eder ve en verimlisini ortaya koyarız.

Karmaşıklık Hesabı:

Algoritmada her adımda yeni bir eleman sıralanmış kısma dahil olmaktadır. Karmaşık hesabında her bir adımda bütün elemanların gezilmesi söz konusu olduğundan en kötü (Worst Case) durumda O(N^2) olacaktır. En iyi ihtimal (Best Case) ise dizinin zaten sıralı veya çoğunlukla sıralı denk gelmesidir. Böyle bir durumda da yine de tüm elemanları kontrol edeceğinden N^2 olacaktır.

Bu konuyla ilgili sorularınızı  alt kısımda bulunan yorumlar alanını kullanarak sorabilirsiniz.

Referanslar

Algoritmalara Giriş:  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

www.mshowto.org

TAGs: Insertion Sort, Sorting Algorithms