Insertion Sort C Kodu Nasıl Yazılır

sokma sıralaması
sokma sıralaması
Öncelikli olarak Inserion Sort Algoritması konusuna hakim olduğunuza emin olmalısınız. Algoritmayı bilmeden kod yazmak mümkün değildir. Bir kodu ezberleyebilirsiniz, ama emin olun unutursunuz. Hiçbir işe yaramaz. Bu yüzden kodları algoritma üzerinden yazmak önemlidir.

Kendimizden alıntı yapacak olursak Insertion Sort Algoritmasının Genel Konsepti şöyledir.




(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.

Bakın aslında bu konsept bize direkt kodları gösteriyor. Bize yalnızca IDE üzerinde yazması kalıyor.

Hemen başlayalım;

N-1 adet geçiş nasıl yapılır? Elbette For döngüsüyle.

for(int i=1;  i<n; i++){} 

Şimdi nasıl n-1 geçiş olacak derseniz i=1 dediğimize dikkat edin derim. Neden 1'den başlattık? Çünkü insertion sort işleminde dizinin ilk elemanını sıralı kabul etmekteyiz.

Şimdi algoritmamızı tekrar hatırlayalım. Bir tane key değeri tutuyorduk. Bu key değerini 0'dan değil, 1'den başlatıyorduk. Bu değeri oluşturalım, unutmayın, bu değer her geçişte 1 kez oluşturulmalı.

for(int i=1;  i<n; i++)
{
         int temp = dizi[i];}


Temp diye bir integer değişken oluştum. Bu değişkene i değerini atadım. Artık her geçişte i değeri bir artacak.

Peki şimdi ne yapacağız? Karşılaştırma işlemi için sıralı dizideki bir önceki elemanla karşılaştırma yapmamız gerekiyor. yani bizim i-1 değerine ihtiyacımız olacak. Onu da j değerinde tutuyorum.

for(int i=1;  i<n; i++)
{
         int temp = dizi[i];
         int j = i-1; 
}
Bakın şimdi Algoritmanın genel konseptine tekrar bakarsak artık karşılaştırma işlemlerini yapacağımız döngüyü oluşturabiliriz. Döngü diyorum, çünkü örneğimizden de gördüğünüz üzere 1 taneden fazla karşılaştırma yapabiliriz. Maksimum dizimizin eleman sayısından 1 eksik olmak üzere karşılaştırma yapılabilir. Bu yüzden bizim döngüye ihtiyacımız var. Ama hangisine? While mı? For mı?

Döngü içerisinde şart oluşturma durumumuz olduğundan While döngüsü burada en uygun döngüdür. Peki şartımız nedir?

Temel şartımız temp değişkenindeki değeri "doğru" yere yerleştirmektir. Unutmayın, önceki elemanları j değişkeni ile kontrol edeceğiz. Doğru yer için temel şart, eğer temp değişkeni, j değişkeninden küçükse j değişkenini bir azaltıp o değerle kontrol etmek, kendisinden büyük değer çıkıncaya kadar döngüyü döndürmektir.

for(int i=1;  i<n; i++)
{
         int temp = dizi[i];
         int j = i-1;
   
         while(temp<dizi[j] && j>=0)
         {
                 dizi[j+1] = dizi[j];
                 j--;
          }

}

for(int i=1; i Bakın While döngüsü şartında temp değişkeni dizi[j] değişkeninden küçük olmalı ve j>=0 olması gerektiğini belirttik. j>=0 şartı j değerini döngü içerisinde sürekli azalttığımızdan ötürü belirttik. Eğer sıfırdan aşağı düşerse while döngüsünden çıksın diye.

Peki While döngüsünün içerisindeki kodlarda ne yaptık? Çok basit! Sadece ve sadece kaydırma yaptık. Yani eğer elimizdeki eleman (temp) karşılaştırma yaptığımız elemandan(dizi[j]) küçükse dizi[j] değerini dizi[j+1]'e atadık. Peki aklınıza şu soru gelebilir, kardeşim, j değeri i-1 değil miydi zaten, neden direkt i yazmadık? Çünkü biz tek bir işlem yapmayacağız, sayı (temp) diğer j değerlerinden ne kadar küçükse o kadar kaydırılacak, ve her kaydırma işleminde eski dizilerin indis değerleri bir artacak ki diziye verileri düzgün kaydedebilelim. işte j-- ifadesi de bundan.

İşimiz bitti mi? Hayır elbette. Biz kaydırmayı yaptık, ama swap işlemini tamamlamadık. Yani sayıları kaydırma kısmı tamamdır, ancak esas Insertion işlemi için atamayı gerçekleştirmedik. Hemen onun kodunu da yazıyorum.

for(int i=1;  i<n; i++)
{
         int temp = dizi[i];
         int j = i-1;
     
         while(temp<dizi[j] && j>=0)
         {
                 dizi[j+1] = dizi[j];
                 j--;
          }
          dizi[j+1] = temp;
}

Burada dikkat etmeniz gereken en önemli konu While döngüsüyle kaydırma yaptıktan sonra doğru noktayı bulmuş olmamız. Doğru noktayı bulduktan sonra while döngüsünden çıkılacak. Çünkü artık temp<dizi[j] şartı sağlanmıyor olacak. Bu yüzden dizi[j+1] = temp ifadesi her geçişin sonunda gerçekleşiyor, yani her geçişte yalnızca 1 tane atama yapıyoruz. While döngüsünde ise doğru noktayı buluyoruz.  Konsept bu, mantık bu.

Bu kod algoritmanın nasıl koda döküleceğine dair bir yaklaşım içermektedir. Bu kod parçacığı çalışmaz, ancak ana algoritmayı içerir. Hazır Insertion Sort C Kodu arıyorsanız ilgili linke bakınız.

Etiketler: , , , ,