Metode Sorting Menggunakan Merge Sort (contoh Script dalam bahasa C++)

MERGE SORT

Metode pengurutan merge sort adalah metode pengurutan lanjut, sama dengan metode Quick Sort. Metode ini juga menggunakan konsep devideand conquer yang membagi data S dalam dua kelompok yaitu S1 dan S2 yang tidak beririsan (disjoint). Proses pembagian data dilakukan secara rekursif sampai data tidak dapat dibagi lagi atau dengan kata lain datadalam sub bagian menjadi tunggal. 

Setelah data tidak dapat dibagi lagi, proses penggabungan (merging) dilakukan antara sub-sub bagian dengan memperhatikan urutan data yang diinginkan (ascending/kecil ke besar atau descending/besar ke kecil). Proses penggabungan ini dilakukan sampai semua data tergabung dan terurut sesuai urutan yang diiginkan. Kompleksitas algoritma merge sort adalah O(n log n).

Cara kerja Merge Sort

Merge Sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya.

Ilustrasi Algoritma Merge Sort

Contoh Program

#include <stdio.h>

#define MAX 5

int Data[MAX];

int temp[MAX];

void merge(int Data[], int temp[], int kiri, int tengah, int kanan)

{

   int i, left_end, num_elements, tmp_pos;

   left_end = tengah - 1;

   tmp_pos = kiri;

   num_elements = kanan - kiri + 1;

   while ((kiri <= left_end) && (tengah <= kanan))

     {

        if (Data[kiri] <= Data[tengah])

        {

            temp[tmp_pos] = Data[kiri];

            tmp_pos = tmp_pos + 1;

            kiri = kiri +1;

        }

        else

        {

            temp[tmp_pos] = Data[tengah];

            tmp_pos = tmp_pos + 1;

            tengah = tengah + 1;

        }

      }

      while (kiri <= left_end)

      {

            temp[tmp_pos] = Data[kiri];

            kiri = kiri + 1;

            tmp_pos = tmp_pos + 1;

      }

      while (tengah <= kanan)

      {

            temp[tmp_pos] = Data[tengah];

            tengah = tengah + 1;

            tmp_pos = tmp_pos + 1;

      }

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

      {

            Data[kanan] = temp[kanan];

            kanan = kanan - 1;

      }

}

void m_sort(int Data[], int temp[], int kiri, int kanan)

{

   int tengah;

   if (kanan > kiri)

   {

       tengah = (kanan + kiri) / 2;

       m_sort(Data, temp, kiri, tengah);

       m_sort(Data, temp, tengah+1, kanan);

       merge(Data, temp, kiri, tengah+1, kanan);

   }

}

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

{

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

}

int main()

{

   int i;

   printf("Masukkan DATA SEBELUM TERURUT : \n");

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

   {

      printf ("Data ke %i : ", i+1);

      scanf ("%d", &Data[i]);

   }

   mergeSort(Data, temp, MAX);

   printf("\nDATA SETELAH TERURUT : ");

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

   printf("%d  ", Data[i]);

   printf("\n");

   //scanf("%d");

   return(0);

}