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 log2n 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ç nlog2n 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.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Yukarıdaki kod, konuyu anlatmak amaçlı olarak verilmiş olup, 2 ve üzeri sayıdaki elemanı olan diziler için tasarlanmıştır. Örneğin 2,4,8,16 gibi boyuttaki dizileri sırayalabilir.
    Sizin diziniz 12 elemanlı olduğu için sorun olmuş.

    Bu durumda kullanabileceğimiz kodu yukarıdaki yazıya ekliyorum. Yeni kodu netbeans ile JAVA dilinde geliştirdim ve dosyaları da indirilebilir şekilde yazıye eklenmiştir.

    Başarılar

  2. Kadir

    Öncelikle merhaba;

    Bu algoritmanın analizine baktığımız zaman O(nlog n) işlem yaptığını görüyoruz, bu algoritmanın performansını hesaplamak isteğimizde n eleman sayısı anlamına geliyorsa sizin örnek verdiğiniz dizi {15, 19, 4, 3, 18, 6, 2, 12, 7, 9, 11, 16} 12 elamandan oluşmakta. Yani benim anladığım kadarı ile n=12, bu algoritmanın performansını herhangi bir soruda cevap olarak O(12log 12) şeklinde mi tanımlamalıyız, cevap olarak bu yeterli mi?

    Cevabınız için şimdiden teşekkürler.

  3. Şadi Evren ŞEKER Article Author

    Evet 12 elemandan oluşan bir listeyi bu algoritma en fazla (bunun altını çiziyorum) 12 x log12 adımda sıralar buradaki logaritma 2 tabanındadır. Dolayısıyla log 12 = 4 olarak bulunur ve 12 x 4 = 48 adımda sıralanması beklenir. Bu en fazla adımdır (upper bound) ve algoritma bundan daha kısa sürede sıralar. Örneğin zaten sıralı bir listeyi hiç sıralamaya da bilir.

    Başarılar

  4. Kadir

    Cevap için çok teşekkürler, ödevimde çok yardımcı oldu;

    Algoritma diziyi sürekli 2 parçaya böldüğü için mi logaritma 2 tabanında oluyor? ( ödevimde yanlış hesap yapmamak için soruyorum.)

    İyi akşamlar.

  5. Utku

    Merhabalar hocam, merge sort'un c dilindeki program kodlarını yazabilir misiniz ? Vidyoyu izledim
    basit bir anlatımla çok rahat anlaşılır bir hale gelmiş çok teşekkür ederim.

  6. öğrenci

    hocam merge sort 3 örnek yapmam gerekiyor bide yazdıgınız bu programı visual studio console application" a mı yazıcaz teşekürler.

  7. talha

    hocam
    k adet sıralı diziyi birlestirmek icin MergeSort algoritmasndaki merge metodunu kullanarak
    once iki sıralı diziyi, sonra elde edilen sıralı dizi ile ucuncu sıralı diziyi
    olacak sekilde tum sonuc sıralı dizilerini bir sonraki sıralı dizi ile birlestirmek

    Birde parcala ve fethet yontemi kullanarak k adet
    diziyi k/2 adet iki tane diziler kumesine bolmek ve sonrasnda k/2 tane dizi ile
    diger k/2 adet diziyi birlestirerek nasıl çözüm üretiriz

    hocam iki taneyi yapıyoruzda k tene nasıl olacak yardım ederseniz sevinirim teşekkürler

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


altı × 3 =