 |
| Insertion Sort |
Sokma sıralaması ismiyle de bilinen Insertion sort mantık olarak iki dizi üzerinde çalışır. Dizilerden birisi sıralı dizi, diğeri ise sırasız, düzensiz dizi olarak kabul edilir.
Dizinin ilk elemanı sıralı dizinin elemanı olarak kabul edilerek düzensiz dizinin ilk elemanıyla karşılaştırılır. Eğer düzensiz dizinin ilk elemanı, düzensiz dizinin son elemanından küçükse düzenli dizide olması gereken yere eklenir.
Tabii yukarıdaki paragraf üzerinden bu algoritmayı anlamak zor. Gelin biz örnek üzerinden yürüyelim. Adım adım insertion sort algoritması nasıl uygulanır ona bir bakalım.
Insertion Sort Uygulaması Örneği
Dizimizin Elemanları; 5 3 7 4 9 2
Sayılarımızı dizi[] değişkeninde tuttuğumuzu varsayıyoruz.
1. Iteration:
Sıralı dizimizin 2. elemanı anahtar indis olarak belirlenir. Çünkü ilk eleman sıralı kabul edilir. Yani dizi[1] = 3 ilk elemandır. Kırmızı renkli Sayı ile Yeşil renkli sayı kıyaslanır.
5 3 7 4 9 2
Karşılaştırma İşlemleri
Yeşil renkli sayı artık sıralı diziye girmeye hak kazanır. Ancak dizi içerisinde karşılaştırılma yapılmadır ki sayı doğru yere eklensin. Algoritmanın adının Insertion yani sokmalı olmasının nedeni tam da budur. 3 sayısı doğru yere sokulmalıdır.
1. karşılaştırma 3 5'ten küçüktür, bu yüzden 5'in önüne yerleştirilir.
3 5 7 4 9 2
Artık sıralı dizimizin elemanları 3 ve 5 oldu.
2. Iteration: Bu geçişte anahtar indis değeri bir artırılır ve dizi[2] olur .Artık anahtar değerimiz dizi[2] olduğuna göre 7 sayısına bakılır. 7 sayısı anahtar değerinin bir eksiği olan sayıyla karşılaştırılmaya başlanır. Yani 5 ile.
3 5 7 4 9 2
Karşılaştırma İşlemleri
1. karşılaştırma: 7 sayısını sıralı dizinin elemanları ile karşılaştırırız. Bütün sayılardan büyük olduğu için yeri aynı kalır. (7>5)
3 5 7 4 9 2
Artık 3 5 7 sayıları sıralıdır.
3. Iteration: Anahtar indis değeri artırılır ve dizi[3] olur. Yani 4 sayısından bir önceki değeri kontrol edeceğiz.
3 5 7 4 9 2
Karşılaştırma İşlemleri
4 sayısını sıralı diziye ekleyebiliriz. Ancak karşılaştırma yaparız.
1. karşılaştırma: 4 sayısı 7'den küçüktür ve 5 sayısıyla karşılaştırma yapılır.
2. karşılaştırma: 4 sayısı 5'ten de küçüktür bu yüzden 3 sayısıyla karşılaştırma yapılır.
3. karşılaştırma: 4 sayısı 3'ten küçük değildir, bu yüzden 3 sayısının indisinin bir fazlasına yerleştirilir.
3 4 5 7 9 2
Artık 3 4 5 7 sayılarımız sıralı olmuştur.
4. Iteration: Anahtar indis değeri artırılarak dizi[4] olur. Artık 9 sayısı ile karşılaştırma yapılır.
3 4 5 7 9 2
Şimdi 9 sayısı sıralı diziye aktarılacak
Karşılaştırma İşlemleri
1. karşılaştırma: 9 sayısı 7'den küçük olmadığı için direkt olduğu yerde kalır. Swap yapılmaz.
3 4 5 7 9 2
9 sayısı artık sıralı dizinin elemanı olur.
5. Iteration: Anahtar indis değeri 5 olur. Yani artık dizi[5] incelenir.
3 4 5 7 9 2
Karşılaştırma İşlemleri
1. karşılaştırma: 2 sayısı 9 ile karşılaştırılır küçük olduğu için 7 ile karşılaştırma yapılır
2. karşılaştırma: 2 sayısı 7'den de küçüktür dolayısıyla 5 ile karşılaştırma yapılır
3. karşılaştırma: 2 sayısı 5'den de küçüktür dolayısıyla 4 ile karşılaştırma yapılır
4. karşılaştırma: 2 sayısı 4'den de küçüktür dolayısıyla 3 ile karşılaştırma yapılır
5. karşılaştırma: 2 sayısı 3'den de küçük olduğu, dizide başka eleman kalmadığı için en başa yerleştirilir.
2 3 4 5 7 9
Böylece dizimiz artık sıralanmıştır.
Insertion Sort Algoritması Genel Konsepti
(Eleman Sayısı - 1) adet Iteration (geçiş) yapılır
Her geçiş içerisinde karşılaştırma işlemleri yapılır. (maksimum n-1 kadar yapılabilir)
Her karşılaştırma işlemi içerisinde sayı doğru yere yerleştirilir.
Insertion Sort C Kodu için ilgili makalemize göz atabilirsiniz.
Etiketler: Adım adım insertion sort algoritması, insertion sort, siralama algoritmaları, sokma sıralaması, sorting algoritmaları
