Merge sort adalah salah satu metode sorting yang mirip dengan metode Quick sort, yaitu melakukan partisi. Algoritma merge sort membagi tabel/array menjadi dua tabel/array yang sama besar. Masing-masing tabel/array diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel/array yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel/array, dua untuk menyimpan elemen dari tabel/array yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel/array, sehingga menghemat ruang atau memori yang dibutuhkan.
Berikut implemenatsi dalam bentuk gambar.
Algoritma Merge umumnya memiliki satu set pointer p0..n yang menunjuk suatu posisi di dalam satu set daftar L0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmanya sebagai berikut:
1. Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.
2. Menemukan pointers points untuk item dengan kunci yang paling rendah; membantu salah satu pointer untuk item yang berikutnya dalam daftar.
Contoh pengurutan dengan metode Merge sort.
Kasus: mengurutkan 50000 bilangan desimal yang diperoleh secara acak menggunakan fungsi srand.
Source code Merge sort menggunakan bahasa C.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <mcheck.h>
/* Fungsi untuk mengurutkan bilangan menggunakan metode Merge Sort */
void mergeS(float *num, int p, int n){
int q = (p + n)/2;
if (p < n){
mergeS(num, p, q);
mergeS(num, q + 1, n);
int i = p;
int j = q + 1;
int k = 0;
float *temp = (float*)malloc((n - p + 1) *sizeof(float));
while ((i <= q) && (j <= n)){
if (num[i] < num[j])
temp[k++] = num[i++];
else
temp[k++] = num[j++];
}
while (i <= q)
temp[k++] = num[i++];
while (j <= n)
temp[k++] = num[j++];
memcpy(num + p, temp, (n - p + 1) *sizeof(int));
free(temp);
}
}
/* Fungsi untuk mencetak bilangan yang sudah terurut */
void printnum(float *num, int n){
int i;
for (i=0; i < n; ++i)
printf("%5.2f \t", num[i]);
printf("\n");
}
/* Fungsi utama */
int main(void){
mtrace();
int i, n, opsi;
float num[50000];
srand( time(NULL) ); /* inisialisasi random seed */
/* Menampung jumlah bilangan yang diinputkan oleh user */
printf("\nMasukkan jumlah bilangan: ");
scanf("%d", &n);
/* Memberi statement jika jumlah bilangan yang diinputkan <= 0 */
if(n <= 0)
printf("\nTidak ada data yang diacak.\n\n");
/* Penelusuran dilanjutkan jika jumlah bilangan yang diinputkan > 0 */
else{
for(i=0; i<n; i++){
num[i] = rand() % 50000 + 1; /* Acak bilangan antara 0..50000 */
num[i] = num[i]/3;
}
printf("\nAcak:\n"); /* Mencetak bilangan yang masih acak */
for(i=0; i<n; i++)
printf("%5.2f \t", num[i]);
/* Menampilkan menu pilihan */
printf("\n\nRandom data dalam array selesai...\n\n");
printf("\nMenu Pilihan:");
printf("\n1) Mengurutkan data dengan MERGE SORT, dan menampilkannya.");
printf("\n2) Selesai.");
do{ /* Menampung menu pilihan yang diinput oleh user */
printf("\n\nPilihan Anda: ");
scanf("%d", &opsi);
switch(opsi){ /* Fungsi untuk mengganti menu pilihan */
case 1:
{
printf("\n# Pengurutan data dengan metode MERGE SORT #\n\n");
mergeS(num, 0, n-1);
printnum(num, n);
}break;
case 2:
{
printf("\nTerima kasih telah mengakses program ini ^_^\n\n");
}break;
}
}
while(opsi!=2);
}
return EXIT_SUCCESS;
}
---oOo---
Program ini dirancang dalam bentuk modular yang terdiri dari beberapa fungsi terkait (berektensi.c) dan fungsi utama yang memiliki fungsi mainsorting (berektensi.c).
Program ini juga dilengkapi dengan command mtrace untuk mengecek apakah pada saat program selesai dijalankan terjadi memory leaks atau tidak, karena pada saat program berjalan terjadi pengalokasian memori. Untuk mengecek mtrace, lakukan command berikut pada terminal:
> export MALLOC_TRACE=mtrace.out
> *run program*
> mtrace *nama file executable*
atau bisa kunjungi URL berikut: http://math.acadiau.ca/ACMMaC/howtos/mtrace.html
Ini merupakan tugas 4 dari mata kuliah Struktur Data saya. Beberapa bagian dari program ini merupakan hasil saduran dari: http://www.google.co.id/search?gcx=w&sourceid=chrome&ie=UTF-8&q=480232e1ad23aTugas_yang_harus_di_upload(1) dengan sedikit modifikasi.
Selamat mencoba, semoga bermanfaat.
"Be optimist, yes we can!"
