Zaman Karmaşıklığı
(Time Complexity)
Aynı Yerde Sıralama Yapabilmesi

(in-place)

En İyi Durum (Best-Case) Ortalama Durum (Average-Case) En Kötü Durum (Worst-Case)
O(nlogn) O(nlogn) O(nlogn) Hayır

Birleştirmeli Sıralama (ing. Merge Sort) algoritması, Böl ve Fethet (ing. Divide and Conquer) problem çözme tekniğine dayanır. Doğal olarak özyinelemeli (ing. recursively) olarak gerçekleştirilmeye çok müsaittir. Birleştirmeli Sıralamanın en büyük avantajı en kötü durumda bile çalışma zamanının O(nlogn) olmasıdır. (En iyi durum ve ortalama durum performansı da O(nlogn)’dir). Rastgele dosyalarla yapılan zaman denemelerinde Birleştirmeli Sıralamanın Hızlı Sıralamadan (ing. Quick Sort) yavaş kaldığı deneyimlense de, Hızlı Sıralamanın bir dezavantaj olarak en kötü durumda O(n2)’e düştüğü bilinmektedir. Ancak Birleştirmeli Sıralamanın ekstra yer ihtiyacı olması ise algoritmanın bu yöntemin dezavantajıdır. Algoritma sıralanacak dizi boyutu kadar fazladan yere ihtiyaç duyar, yani algoritmanın yer karmaşıklığı (ing. space complexity) O(n)’dir. (yani algoritma “in-place” değil)

Algoritma temel olarak iki safhaya ayrılabilir. Bunlar birinci safha olan “bölme” ve ikinci safha olan “birleştirme”dir. Algoritmayı daha kolay kavrayabilmek için önce ikinci safha olan ve zaten algoritmaya adını da veren “birleştirme” safhasından başlayalım.

Birleştirme safhasında kullanılan algoritma, basit bir şekilde iki sıralı diziyi birleştirmeye yarayan etkin bir işlem. Bir örnek üzerinde açıklamak gerekirse :

Elimizde aşağıdaki şekilde iki kendi içinde sıralı dizi olsun. Bizim amacımız bu iki diziyi yine sıralı bir şekilde üçüncü bir dizide toplamak (ekstra yer ihtiyacımız olduğuna dikkat edin, örneğin burada ekstra 8 elemanlık boş bir diziye ihtiyacımız var.)

1 3 5 6             2 4 7 8

Algoritma şu şekilde çalışıyor. En başta iki dizinin de ilk elemanını gösteren işaretçilerimiz var. Bu işaretçilerin gösterdiği yerdeki elemanları karşılaştırıyoruz. Örneğin bizim örneğimizde 1 2’den küçük olduğu için yeni dizimize 1’i yazıyoruz ve sadece o işaretçiyi bir sağa kaydırıyoruz. Yani ilk dizinin işaretçisi artık 3’ü gösteriyor. İşaretçilerin gösterdikleri yerlerdeki değerleri tekrar karşılaştırınca bu sefer ikinci dizideki 2 değerinin 3’ten küçük olduğunu görüp onu alıyoruz ve bu sefer sadece o işaretçiyi bir sağa kaydırıyoruz ve işlem bu şekilde sürüyor. Eğer diğer dizideki elemanlar bitmeden herhangi bir dizinin sonuna gelirsek, öteki dizideki elemanları zaten hiç karşılaştırma yapmadan yeni diziye kopyalıyoruz. (bizim örneğimizi çalıştırırsanız ilk dizinin önce biteceğini görürsünüz ve ikinci dizde kalan 7 ve 8 sayıları doğrudan yeni dizye kopyalanabilir). Bu algoritmayı çalıştırsanız işin sonunda üstteki diziler için yeni dizimizin 1 2 3 4 5 6 7 8 şeklinde sıralı olacağını rahatlıkla bulabilirsiniz. (Sıralı iki dizi üzerinde çalışan bu algoritma en kötü durumda bile O(n) zamanında çalışan etkin bir algoritmadır).

Fakat dikkat ettiyseniz burada iki farklı dizi var ve bu iki dizi de sıralı. Bize ise tek sırasız bir dizi veriliyor ve algoritmanın bu diziyi sıralı hale getirmesi bekleniyor. Bu durumda algoritma yukarıda açıklanan “birleştirme” safhasına geçebilmek için “sıralı” dizilere ihtiyaç duyacaktır. Peki bir dizinin sıralı olduğundan nasıl emin olabiliriz? Yani hangi dizilerin sıralı olduğu garantidir? Tabiki dizi tek elemanlı ise !

Bu nedenle Birleştirmeli Sıralama algoritması ilk önce tüm diziyi her eleman yalnız kalacak şekilde bölüyor ve daha sonra bu elemanları teker teker yukarıda açıkladığımız algoritma ile birleştiriyor. Örneğimiz üzerinden gidersek :

9 2 5 10 1 4 6 3 8 7

Önce ana dizi ikiye bölünüyor.

9 2 5 10 1            4 6 3 8 7

Daha sonra bu diziler tekrar ve tekrar içlerinde tek eleman kalana kadar ikiye bölünmeye devam ediyor.

9 2 5   10 1                          4 6 3   8 7  (tam olarak ikiye bölünemeyen durumlarda fazla olan kısmı sol veya sağ tarafa almamız sonucu değiştirmez)

9 2   5     10   1                    4 6   3           8   7

9   2                                      4   6

Bu noktada artık tüm alt diziler tek elemanlı. Artık yukarıda açıkladığımız “birleştirme” safhasına geçebiliriz.

Tüm elemanlar nereden bölündüler ise aynı yerden birleşmeye başlıyorlar. (birleştirdiklerimizin arasına “-” işareti koyduk)

2-9                                       4-6

2-5-9        1-10                    3-4-6       7-8

1-2-5-9-10             3-4-6-7-8

1-2-3-4-5-6-7-8-9-10

Algoritmanın Java dilinde yazılmış örnek kodları aşağıdan incelenebilir.

public static void mergeSort(int[] a)
{
   int[] tmpArray = new int[a.length];

   mergeSort( a, tmpArray, 0, a.length - 1 );
}

private static void mergeSort(int[] a, int[] tmpArray, int left, int right)
{
   if( left < right )
   {
	int center = ( left + right ) / 2;
	mergeSort( a, tmpArray, left, center );
	mergeSort( a, tmpArray, center + 1, right );
	merge( a, tmpArray, left, center + 1, right );
   }
}

private static void merge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd )
{
   int leftEnd = rightPos - 1;
   int tmpPos = leftPos;
   int numElements = rightEnd - leftPos + 1;

   while( leftPos <= leftEnd && rightPos <= rightEnd )
	if( a[ leftPos ] <= a[ rightPos ] )
	   tmpArray[ tmpPos++ ] = a[ leftPos++ ];
	else
	   tmpArray[ tmpPos++ ] = a[ rightPos++ ];

   while( leftPos <= leftEnd )    
	tmpArray[ tmpPos++ ] = a[ leftPos++ ];

   while( rightPos <= rightEnd )  
	tmpArray[ tmpPos++ ] = a[ rightPos++ ];

   for( int i = 0; i < numElements; i++, rightEnd-- )
	a[ rightEnd ] = tmpArray[ rightEnd ];
}

Kodda “tmpArray” adında ve sıralanacak dizi boyutlarında bir yardımcı dizi yaratıldığına dikkat edin. Üçüncü metod olan “merge” metodunun birleştirme işlemi yaptığını anlamışsınızdır. Tabiki elimizde iki ayrı dizi var ve biz bunları birleştiriyor değiliz; ana dizimiz bölündükten sonra tüm işlemler yine bunun üzerinde yapılıyor. Dizinin pozisyonlarını doğru belirlediğimizde, elimizde sanki farklı diziler varmış gibi düşünebiliyoruz.

2 thoughts on “Birleştirmeli Sıralama (Merge Sort)

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak.