Metode Merge Sort dengan C / C++

Merge sort merupakan algoritma pengurutan dalam ilmu komputeryang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.
Prinsip utama yang diimplementasikan pada algoritma merge-sortseringkali disebut sebagai pecah-belah dan taklukkan ( divide and conquer). Cara kerja algoritma 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.

untuk listingnya silahkan di ketik seperti pada tulisan dibawah ini:


#include <stdio.h>
#define MAX 10
int Data[MAX];
int temp[MAX];


// Prosedur merge sort
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;
}
}
// Prosedur membuat kumpulan data
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);
}
setelah sobat mengcopy listing diatas coba dijalankan lebih kurang hasilnya seperti pada gambar dibawah ini

Sumber: http://aslangpemrograman.blogspot.com/2012/05/tutorial-c-c-metode-merge-sort.html