Birleştirme Sıralaması (Merge Sort)

Yazan : Şadi Evren ŞEKER

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan diziyi ikişer elemanı kalan parçalara inene kadar sürekli olarak ikiye böler. Sonra bu parçaları kendi içlerinde sıralayarak birleştirir. Sonuçta elde edilen dizi sıralı dizinin kendisidir. Bu açıdan bir parçala fethet (divide and conquere) yaklaşımıdır.

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3,7

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Birleştirme sıralamasının çalışması yukarıdaki bu örnek dizi üzerinde adım adım gösterilmiştir. Öncelikle parçalama adımları gelir. Bu adımlar aşağıdadır.

1. adım diziyi ikiye böl:

5,7,2,9 ve 6,1,3,7

2. adım çıkan bu dizileri de ikiye böl:

5,7 ; 2,9 ; 6,1 ; 3,7

3. adım elde edilen parçalar 2 veya daha küçük eleman sayısına ulaştığı için dur (aksi durumda bölme işlemi devam edecekti)

4. adım her parçayı kendi içinde sırala

5,7 ; 2,9 ; 1,6 ; 3,7

5. Her bölünmüş parçayı birleştir ve birleştirirken sıraya dikkat ederek birleştir (1. ve 2. parçalar ile 3. ve 4. parçalar aynı gruptan bölünmüştü)

2,5,7,9 ve 1,3,6,7
6. adım, tek bir bütün parça olmadığı için birleştirmeye devam et

1,2,3,5,6,7,7,9

7. adım sonuçta bir bütün birleşmiş parça olduğu için dur. İşte bu sonuç dizisi ilk dizinin sıralanmış halidir.

Birleştirme Sıralamasının JAVA dilinde yazılmış bir örnek kodu aşağıda verilmiştir:

Öncelikle birleştirme sıralamasının ana fonksiyonu:

   public int [] mergesort(int [] m)
   {

     int x=0;
     int y=0;
     int middle=m.length/2;
     int left[] =new int [middle];
     int right[] =new int [middle];
     int result[] =new int[(m.length)];

     if(m.length<= 1){
       return m;
     }

     for(int i=0; i<middle; i++)
     {
       left[x]=m[i];
       x++;
     }
     for(int i=middle; i<m.length; i++)
     {
       right[y]=m[i];
       y++;
     }
     left=mergesort(left);
     right=mergesort(right);
     result=merge(left,right);
     return result;
   }

Yukarıdaki bu fonksiyon dikkat edilirse özyinelemeli (recursive) bir kod olup paramatre olarak aldığı dizinin yanında bu dizi boyutunun yarısı uzunluğunda iki ilave dizi kullanmış ve bu dizilere iki parçayı ayrı ayrı koyarak yine sıralaması için kendi fonksiyonuna parametre olarak geçirmiştir. Sonda ise bu iki parçayı birleştiren bir merge() fonksiyonu çağırmıştır. İşte bu birleştirme fonksiyonunun kodu aşağıda verilmiştir:

public int [] merge(int []left,int []right)
 {
   int result[] =new int [left.length + right.length];

     int x=0;
     int y=0;
     int k=0;

   while(left.length>x && right.length>y)

   {

     if(left[x] <= right[y])

     {

       result[k]=left[x];
       x++;
       k++;

     }

     else

      {
        result[k]=right[y];
        y++;
        k++;

      }
   }

   if(left.length>x)

   {
     while(x < left.length)

     {

     result[k]=left[x];
     x++;
     k++;

     }
   }

   if(right.length>y)

   {
     while(y < right.length)

     {

     result[k]=right[y];
     y++;
     k++;

     }
   }
   return result;
 }

Yukarıdaki koda dikkat edilecek olursa 3 ayrı durum için birleştirme kodu yazılmıştır:

Birinci durumda iki dizide de eleman bulunmaktadır. Bu durumda iki dizideki en baştaki sayılar karşılaştırılarak küçük olan sonuç dizisine kopyalanmaktadır. İkinci ve üçüncü durumlarda ise dizilerden birisinde eleman kalmamıştır. Bu durumlarda eleman kalan dizideki elemanlar doğrudan sonuç dizisine kopyalanabilir.

Birleştirme Sıralamasının algoritma karmaşıklığına bakıldığında O(nlogn) olarak bulunur çünkü üzerinde çalışılan dizi her adımda 2ye bölünmüştür böylece sonuç dizisi olan 2şer elemanlı dizilere log₂n adımda ulaşılabilir. Daha sonra her n eleman için sıralama yapıldığı ve her n eleman üzerinden geçildiği için bu değer çarpan olarak gelmekte ve sonuç nlog₂n olarak bulunmaktadır.

« Yığınlama Sıralaması (Heap Sort) | Hızlı Sıralama Algoritması (Quick Sort Algorithm) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Birleştirme Sıralaması (Merge Sort)' isimli yazı 09 Aug 2008 tarihinde, saat: 21:55 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 3413 defa okunmuştur.

Benzer yazıları JAVA, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar