Merge Sort C Kodu Nasıl Yazılır?

Merge sort divide and conqueror algoritması kullandığı için kodlama süreci biraz uzundur. (ezberci öğrenciler için kötü haber :) ) Ancak mantığını bilirsek her şeyi kodlamak kolaydır. Biz bu yüzden algoritmanın mantığını önceden anlatıyoruz. Eğer Merge Sort Algoritması konusunu hatırlamak isterseniz linke tekrar bakın. Çünkü oradaki mantık ekseninde kodlama yapacağız.

Şimdi Merge Sort konusunu tek fonksiyon ile halledemeyiz, bize iki tane fonksiyon lazım. Bir tanesi diziyi alt dizilere ayıracak, diğeri ise ayrılmış dizileri sıralayarak birleştirecek.

birleştirmeli sıralama
Merge Sort C kodu nasıl yazılır


Merge Sort Alt Dizilere Ayırma Fonksiyonu


Normal anlatımlarımda fonksiyon yazmıyor, yalnızca algoritmanın ana kodlarını yazıyordum. Ama bu konuda değişiklik yapıyorum.

void parcalaraBol(int dizi[], int sol, int sag)
{
}

void türünde bir fonksiyon oluşturuyoruz. Bu fonksiyon dizi, sol ve sağ parametreleri alıyor. Dizi parametresini anlatmama gerek yok. Mevcut dizimiz işte, int sol ifadesi dizimizin en başında yer alan indistir. Bakın değer değil, indis buradaki mesele. int sag ise dizimizin en sonundaki (sağındaki) indistir.

Fonksiyonumuz dizimizi sürekli alt parçalara böleceği için limit koymamız lazım. Sonsuza kadar bölemez. 1'er elemanlı dizilerimiz oluştuktan sonra bölme işlemi sonlanmalı. Peki şartımız ne olmalı? Elimizdeki değerlere bakalım hemen, sol ve sağ değişkenlerimiz mevcut. Eğer bir dizinin sol ve sağ değerleri aynıysa işlem sona ermeli. Çünkü 1 elemanlı dizinin sol ve sağ değeri aynıdır. O zaman şart olarak sol değeri sag değerinden küçük olmalı şartı işimizi görecektir.

void parcalaraBol(int dizi[], int sol, int sag)
{
              if(sol<sag)
              {}
}

Şartımızı oluşturduk, dizimizi bu şekilde böleceğiz. Peki ama bir dizi ikiye nasıl bölünür? yani 8 elemanlı bir diziyi ikiye böldüğümüzde 4 elemanlı iki dizi oluşturmamız lazım. Ben burada Iterative bir yaklaşım yerine Merge Sort'da sıklıkla kullanılan Recursive bir yaklaşım izleyeceğim. Ama önce en temel mantığın noktasını bulalım. Bir dizi nasıl ikiye bölünür?

void parcalaraBol(int dizi[], int sol, int sag)
{
              if(sol<sag)
              {
                     int mid = left + (right-left)/2;
              }
}



Şimdi Recursive fonksiyon yazacağımız noktaya geldik. Çünkü tek bir bölme işlemi yapmayacağız, elbette iterative çözüm de üretilebilir, ancak recursive fonksiyon ile işimizi çok kolay halledebiliriz.

void parcalaraBol(int dizi[], int sol, int sag)
{
              if(sol<sag)
              {
                     int mid = left + (right-1)/2;
                 
                     parcalaraBol(dizi, sol, mid);
                     parcalaraBol(dizi, mid+1, sag);
              }
}

Recursive fonksiyonları bildiğinizi varsayıyorum, burada olan işlem dizinin sol ve sağ parçalarını sürekli ikiye ayrılmasıdır. Yani fonksiyon her seferinde kendisini çağırıyor ve diziyi ikiye bölüyor. Ama kodumuz burada bitemez, çünkü bu ayırdıklarımızı bir de birleştirmemiz gerekiyor. İşte bunu ayrı bir fonksiyon olarak yazacağız, ancan bu oluşturduğumuz fonksiyonun içerisinden merge fonksiyonunu yine recursive olarak çağırmamız lazım. Yani iş bu fonksiyonun içerisinde bitsin.

void parcalaraBol(int dizi[], int sol, int sag)
{
              if(sol<sag)
              {
                     int mid = left + (right-1)/2;
                 
                     parcalaraBol(dizi, sol, mid);
                     parcalaraBol(dizi, mid+1, sag);

                     birlestir(dizi, sol, mid, sag);
              }
}


Şimdi birlestir fonksiyonunu yazalım. Esas olay burası zaten, bölmesi her zaman kolaydır ;) zor olan ise birleştirmek. Daha zor olanı ise üzerinde işlem uygulayarak birleştirmek.

Merge Sort Birleştirme Fonksiyonu


Şimdi fonksiyonumuzu başlatalım.

void birlestir(int dizi[], int sol, int orta, int sag)
{}

Fonksiyonumuza 4 tane parametre yolluyoruz.

Şimdi algoritmamızı tekrar hatırlayalım. En küçük parçalara ayırdıktan sonra birleştirme işlemi uyguluyorduk. Yani iki adet tek elemandan oluşan diziyi 2 elemanlı tek dizi haline getiriyorduk. Bize kendimizin oluşturabileceği diziler lazım. Elimizdeki dizi işimizi görmez çünkü. Ama onların boyutları ne olacak? ilk sorun bu. Çünkü 1. aşamada 2 elemanlı dizi oluştururken 2. aşamada 4 elemanlı bir dizi oluştururuz. Bu yüzden boyut kısmı statik olamaz, dinamik olmalı.

void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;
}

n1 ve n2 olmak üzere iki değişken oluşturdum. n1 sol için, n2 sağ için. mid-sol+1 değeri sol tarafın eleman sayısını verir. +1 değeri indisler 0'dan başladığı için uygulanır. n2 ise sag indisle mid farkı kadar.

Şimdi dizilerimizi oluşturalım.

void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;

              int solDizi[n1], sagDizi[n2];
}

Gördügünüz üzere solDizi ve sagDizi olmak üzere iki dizi oluşturdum. Bunların boyutlarına da n1 ve n2 değerlerini atadım.

Şimdi oluşturduğumuz bu dizilere elemanlarını kopyalamamız gerekiyor. Bize iki tane for döngüsü lazım.

void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;

              int solDizi[n1], sagDizi[n2];

              for(int i=0; i<n1; i++)
                   solDizi[i] = dizi[sol+i];
              for(int j=0; j<n2; j++)
                   sagDizi[j] = dizi[orta+1+j];
}

solDizi ve sagDizi değerlerini tek tek oluşturduk. Artık karşılaştırma yaparak birleştirme işlemlerini gerçekleştirebilirsiniz.

Sayaçlarımı tekrar kullanmak istediğim için i = 0 ve j = 0 değerini oluşturuyorum. Unutmayın, i ve j değerleri yukarıdaki for döngülerinde arttı. Bunun da yanında sol taraf daima karşılaştırma yapacağımızda başlangıç değerini oluşturacağı için onu da bir değişkene atıyorum.

void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;

              int solDizi[n1], sagDizi[n2];

              for(int i=0; i<n1; i++)
                   solDizi[i] = dizi[sol+i];
              for(int j=0; j<n2; j++)
                   sagDizi[j] = dizi[orta+1+j];

              i = 0;
              j = 0;
              k = sol;
}

Şimdi bundan sonraki işlemler çetrefilli, 3 ayrı durumu gözetleyerek kod yazmak zorundayız. Aslında algoritmayı adım adım uygularken görmüştük. Karşılaştırmaları nasıl yapıyorduk? ilk önce soldaki dizinin ilk elemanını sağdaki dizinin ilk elemanı ile karşılaştırıyorduk. Küçük olanı, üstteki dizinin ilk elemanı olarak yazıyorduk. İşte bunun kodunu yazacağız şimdi.

void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;

              int solDizi[n1], sagDizi[n2];

              for(int i=0; i<n1; i++)
                   solDizi[i] = dizi[sol+i];
              for(int j=0; j<n2; j++)
                   sagDizi[j] = dizi[orta+1+j];

              i = 0;
              j = 0;
              k = sol;

              while(i < n1 && j<n2)
              {

                }
}

İlk olarak loop'umuzu oluşturduk, loopumuz i değişkenimiz n1'den küçük olduğu ve j değişkenimizin n2'den küçük olduğu durumlarda çalışacak. Her loop içerisinde i ve j değerleri artırılacak. Ancak şartımız bozulduğunda while döngüsünden çıkılacak. Elbette döngüden çıkıldığında işlemler bitmeyeceğinden iki farklı şart daha yazmamız gerekecek. Ama o sonraki iş. Şimdi while döngüsünün içerisinde ne yapacağız ona bakalım. küçük parçalar birleştirilecek ve büyük bir dizi oluşturulacak. Mantığı aşağıya yazıyorum;

1- soldaki dizinin ilk elemanı ile sağdaki dizinin ilk elemanı karşılaştırılır.
2- hangisi küçükse birleştirilmiş dizinin ilk boşta olan indisine yerleştirilir.


void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;

              int solDizi[n1], sagDizi[n2];

              for(int i=0; i<n1; i++)
                   solDizi[i] = dizi[sol+i];
              for(int j=0; j<n2; j++)
                   sagDizi[j] = dizi[orta+1+j];

              i = 0;
              j = 0;
              k = sol;

              while(i < n1 && j<n2)
              {
                     if(solDizi[i] < sagDizi[j])
                     {
                             Dizi[k] = solDizi[i];
                             i++;
                      } else {
                             Dizi[k] = sagDizi[j];
                             j++
                      }
                      k++;
               }
}

Evet, üstteki dizide birleştirme işlemlerini yaptık. Ancak ufak bir sorun var. Her şey istediğimiz gibi gitmeyebilir, yani bir bakmışız ki, soldaki dizinin tüm elemanları üstteki diziye yerleşmiş, sağdaki dizi aynen kalmış, ya da tersi olmuş olabilir. İşte bu noktada işlerimizi düzenleyecek bir koda daha ihtiyacımız var. Yani elimizde kalan elemanları üstteki büyük diziye iteleyeceğiz.

void birlestir(int dizi[], int sol, int orta, int sag)
{
              int n1 = (mid-sol)+1;
              int n2 = sag-mid;

              int solDizi[n1], sagDizi[n2];

              for(int i=0; i<n1; i++)
                   solDizi[i] = dizi[sol+i];
              for(int j=0; j<n2; j++)
                   sagDizi[j] = dizi[orta+1+j];

              i = 0;
              j = 0;
              k = sol;

              while(i < n1 && j<n2)
              {
                     if(solDizi[i] < sagDizi[j])
                     {
                             Dizi[k] = solDizi[i];
                             i++;
                      } else {
                             Dizi[k] = sagDizi[j];
                             j++
                      }
                      k++;
               }

              while(i<n1)
              {
                      dizi[k] = solDizi[i];
                      i++;
                      k++;
               }
          
              while(j < n2)
              {
                       dizi[k] = sagDizi[j];
                       j++;
                       k++;
               }
}

Oh be, uzun oldu ama değdi bence. Merge Sort'un c kodlarını bu şekilde yazabiliriz. Ben size hazır kodları vereceğim bir sonraki yazımda. Hatta siz bunu okurken yazmış olurum. Merge Sort Hazır C Kodu linkine tıklarsanız kolayca ulaşabilirsiniz.

Etiketler: , , ,