Merge Sort Algoritması (Birleştirmeli Sıralama)

Merge Sort algoritması (Birleştirmeli Sıralama) nedir? Ne için kullanılır?

Birleşmeli Sıralama, bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

Merge Sort algoritması adımları

1. adım diziyi ikiye böl.

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

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. 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ü)

6. adım, tek bir bütün parça olmadığı için birleştirmeye devam et.

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.

Bir örnek yapalım

Sıralamak istediğimiz dizi şu şekilde olsun:

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

İşlemlerimizi adım adım gerçekleştirelim.

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.

Kodlama

Python, Java ve C dillerinde ise şu şekilde yazabiliriz.

JAVA

public class Sorting
{
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;

// Ana döngü
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ] <= a[ rightPos ] )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

while( leftPos <= leftEnd ) // İlk yarının kalanını kopyalıyoruz
tmpArray[ tmpPos++ ] = a[ leftPos++ ];

while( rightPos <= rightEnd ) // Sağdaki yarının kalanını kopyalıyoruz
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

// tmpArray'i tekrar kopyalıyoruz
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}

PYTHON

def mergeSort(arr):
   if len(arr) >1:
      mid = len(arr)//2 #Dizinin yarısını buluyoruz
      L = arr[:mid] # Diziyi ikiye ayırıyoruz
      R = arr[mid:]
      mergeSort(L) # İlk yarıyı sıralıyoruz
      mergeSort(R) # İkinci yarıyı sıralıyoruz
      i = j = k = 0
      # dataları geçici dizilere kopyalıyoruz L[] ve R[]
      while i < len(L) and j < len(R):
         if L[i] < R[j]:
            arr[k] = L[i]
            i+=1
         else:
            arr[k] = R[j]
            j+=1
         k+=1
      # Eleman kalıp kalmadığını kontrol ediyoruz
      while i < len(L):
         arr[k] = L[i]
         i+=1
         k+=1
      while j < len(R):
         arr[k] = R[j]
         j+=1
         k+=1
# Listeyi yazdırma fonksiyonu
def printList(arr):
   for i in range(len(arr)):
      print(arr[i],end=" ")
   print()

C

#include<stdlib.h>
#include<stdio.h>

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/*Geçici diziler oluşturuyoruz */
int L[n1], R[n2];

/* Verileri geçici dizilere kopyalıyoruz L[] veR[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/*Kalan elemanları kontrol edip varsa onları geçici dizilere kopyalıyoruz*/
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;

// İlk ve ikinci yarıları sıralıyoruz
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

/* Diziyi yazdırma fonksiyonu */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}