Merge Sort

Pengurutan algoritma Merge Sort membuat pengurutan dengan membagi 2 dan menggabungkannya. Metoda ini cukup efisien untuk diterapkan. Sama dengan Quick Sort, algoritma Merge Sort adalah dasar pembagian dan penyelesaiannya. Pertama urutan atau elemen data awal diurutkan dengan membaginya menjadi 2 bagian (Devide). Setengahnya diurutkan dengan bebas (Conquer). Kemudian 2 bagian itu digabungkan dengan cara diurut sesuai dengan urutan (Combine).

Pertama, index m yang berada di tengah diantara lo dan hi adalah faktor. Kemudian urutan pertama( dari lo ke m ) dan bagian kedua ( dari m+1 ke hi ) diurutkan berulang yang disebut mergesort. Kemudian dua bagian yang sudah diurutkan digabungkan oleh procedure merge. Perulangan berakhir ketika lo = hi, dan ketika yang berikutnya hanya memiliki satu elemen.

Algoritma Merge Sort

Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer.

Algoritma untuk Merge Sort adalah sebagai berikut :

1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)

2. Untuk kasus n>1, maka :

a.       DIVIDE: Bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.

b.      CONQUER: Secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.

MERGE: Gabungan hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.

Algoritma

Procedure MergeSort(input/output A : TabelInt, input i, j : integer)

{ Mengurutkan tabel A[i..j] dengan algoritma Merge Sort

Masukan: Tabel A dengan n elemen

Keluaran: Tabel A yang terurut }

Deklarasi:

k : integer

Algoritma:

if i { Ukuran(A)> 1}

k←(i+j) div 2

MergeSort(A, i, k)

MergeSort(A, k+1, j)

Merge(A, i, k, j)

Endif

procedure Merge(input/outputA : TabelInt, input kiri,tengah,kanan : integer)

{ Menggabung tabel A[kiri..tengah] dan tabel A[tengah+1..kanan] menjadi tabel A[kiri..kanan] yang terurut menaik.

Masukan: A[kiri..tengah] dan tabel A[tengah+1..kanan] yang sudah terurut menaik.

Keluaran: A[kiri..kanan] yang terurut menaik. }

Deklarasi

B : TabelInt

i, kidal1, kidal2 : integer

Algoritma:

kidal1←kiri { A[kiri .. tengah] }

kidal2←tengah + 1 { A[tengah+1 .. kanan] }

i←kiri

while (kidal1 ≤ tengah) and (kidal2 ≤ kanan) do

if Akidal1 ≤ Akidal2 then

Bi←Akidal1

kidal1←kidal1 + 1

else

Bi←Akidal2

kidal2←kidal2 + 1

endif

i←i + 1

endwhile

{ kidal1 > tengah or kidal2 > kanan }

{ salin sisa A bagian kiri ke B, jika ada }

while (kidal1 ≤ tengah) do

Bi←Akidal1

kidal1←kidal1 + 1

i←i + 1

endwhile

{ kidal1 > tengah }

{ salin sisa A bagian kanan ke B, jika ada }

while (kidal2 ≤ kanan) do

Bi←Akidal2

kidal2←kidal2 + 1  i←i + 1

endwhile

{ kidal2 > kanan }

{ salin kembali elemen-elemen tabel B ke A }

for i←kiri to kanan do

Ai←Bi

endfor

{ diperoleh tabel A yang terurut membesar }

Source Code Algoritma Merge Sort

#include

#include

#define NUM_ITEMS 100

void mergeSort(int numbers[],int temp[],int array_size);

void m_sort(int numbers[],int temp[],int left,int right);

void merge(int numbers[],int temp[],int left,int mid,int right);

int numbers[NUM_ITEMS];

int temp[NUM_ITEMS];

int counter;

int main()

{

 int i;//seed random number generator

 srand(getpid());//fill array with random integers

 for (i = 0;i < NUM_ITEMS;i++)

 numbers[i] = rand();

 mergeSort(numbers,temp,NUM_ITEMS);//perform merge sort on array

 for (i = 0;i < NUM_ITEMS;i++)

 printf("%i\n",numbers[i]);

 printf("Done with sort.\n");

 printf("%i %i\n",i,counter);

}

void mergeSort(int numbers[],int temp[],int array_size)

{

 m_sort(numbers,temp,0,array_size - 1);

}

void m_sort(int numbers[],int temp[],int left,int right)

{

 int mid;

 if (right > left)

{

 mid = (right + left) / 2;

 m_sort(numbers,temp,left,mid);

 m_sort(numbers,temp,mid+1,right);

 merge(numbers,temp,left,mid+1,right);

 }

 counter++;

}

void merge(int numbers[],int temp[],int left,int mid,int right)

{

 int i,left_end,num_elements,tmp_pos;

 left_end = mid –1;

 tmp_pos = left;

 num_elements = right –left + 1;

 while ((left <= left_end) &&(mid <= right))

{

 if (numbers[left] <= numbers[mid])

 {

 temp[tmp_pos] = numbers[left];

 tmp_pos = tmp_pos + 1;

 left = left +1;

 }

 else

 {

 temp[tmp_pos] = numbers[mid];

 tmp_pos = tmp_pos + 1;

 mid = mid + 1;

 }

counter++;

 }

 while (left <= left_end)

{

 temp[tmp_pos] = numbers[left];

 left = left + 1;

 tmp_pos = tmp_pos + 1;

counter++;

 }

 while (mid <= right)

{

 temp[tmp_pos] = numbers[mid];

 mid = mid + 1;

 tmp_pos = tmp_pos + 1;

counter++;

 }

 for (i=0;i <= num_elements;i++)

{

 numbers[right] = temp[right];

 right = right - 1;

counter++;

 }

}