Tutorial C / C++ Metode Merge Sort

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang 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-sort seringkali 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




oke deh sobat..
selesai program kecil kita ini,
selamat berkarya...

Tweet