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.

[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/video/mergesort.flv /]

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.

Yukarıdaki kodun bir problemi, sıralama işlemi sırasında 2 ve üzeri sayıdaki elemanlı dizileri kabul ediyor olmasıdır. Örneğin 2,4,8,16 gibi eleman sayılarındaki diziyi kabul eder. Bunun sebebi, sıralama fonksiyonuna gelen dizinin her durumda iki eşit parçaya bölünmesidir. Oysaki tek eleman sayısına sahip dizilerde, bölünme sonucunda sorun çıkar. Örneğin 3 elemanlı bir diziyi iki parçaya böldüğümüzde biri 2 diğeri 1 elemanlı iki dizi elde etmemiz gerekir. Bu durumda bölme işlemi sonucunda tek elemana inen eleman sayıları için de geçerlidir. Örneğin 12 elemalı bir dizi önce 6+6 şeklinde eşit iki parçaya sonra 6 elemalı diziler 3+3 şeklinde eşit parçalara ve nihayet 3 elemalı dizi eşit olmayan iki parçaya bölünecektir. Bu durumda sorunun çözümü için yukarıdaki koda, ilgili düzeltmeyi yapmamız gerekir.

JAVA dili için yukarıdaki kodu düzenleyerek tekrar yazdım ve kod aşağıdaki şekildedir:

public class MergeSort {

    private int[] list;

   // siralancak listeyi alan inşa fonksiyonu
    public MergeSort(int[] listToSort) {
	list = listToSort;
    }

   // listeyi döndüren kapsülleme fonksiyonu 
    public int[] getList() {
	return list;
    }

   // dışarıdan çağırılan sıralama fonksiyonu
    public void sort() {
	list = sort(list);
    }

  // Özyineli olarak çalışan ve her parça için kullanılan sıralama fonksiyonu
    private int[] sort(int[] whole) {
	if (whole.length == 1) {
	    return whole;
	}
	else {
	   // diziyi ikiye bölüyoruz ve solu oluşturuyoruz
	    int[] left = new int[whole.length/2];
	    System.arraycopy(whole, 0, left, 0, left.length);

	    //dizinin sağını oluşturuyoruz ancak tek sayı ihtimali var
	    int[] right = new int[whole.length-left.length];
	    System.arraycopy(whole, left.length, right, 0, right.length);

	    // her iki tarafı ayrı ayrı sıralıyoruz
	    left = sort(left);
	    right = sort(right);

	    // Sıralanmış dizileri birleştiriyoruz
	    merge(left, right, whole);

	    return whole;
	}
    }

    // birleştirme fonksiyonu
    private void merge(int[] left, int[] right, int[] result) {
	int x = 0;
	int y = 0;
	int k = 0;

	// iki dizide de eleman varken
	while (x < left.length &&
	       y < right.length) {
	    if (left[x] < right[y]) {
		result[k] = left[x];
		x++;
	    }
	    else {
		result[k] = right[y];
		y++;
	    }
	    k++;
	}

	int[] rest;
	int restIndex;
	if (x >= left.length) {

	    rest = right;
	    restIndex = y;
	}
	else {

	    rest = left;
	    restIndex = x;
	}

	for (int i=restIndex; i<rest.length; i++) {
	    result[k] = rest[i];
	    k++;
	}
    }

    public static void main(String[] args) {

	int[] arrayToSort = {15, 19, 4, 3, 18, 6, 2, 12, 7, 9, 11, 16};

	System.out.println("Unsorted:");
	for(int i = 0;i< arrayToSort.length ; i++){
            System.out.println(arrayToSort[i] + " ");
        }

	MergeSort sortObj = new MergeSort(arrayToSort);
	sortObj.sort();

	System.out.println("Sorted:");
        int [] sirali = sortObj.getList();

        for(int i = 0;i< sirali.length ; i++){
            System.out.println(sirali[i] + " ");
        }

    }
}

Gerekli açıklamaları kod içerisine yorum olarak yazdım.