Merge Sort

Algoritma Merge Sort

Algoritma Merge adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data mu. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

    Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

    Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

    Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data

    berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Misalkan kita mau mengurutkan beberapa angka yaitu 38,27,43,3,9,82 dan 10. Maka untuk mengurutkan menggunakan merge-sort langkah-langkahnya seperti gambar dibawah ini 

Algoritma untuk prosedur MergeSortnya :

mergesort(low, high) { int mid; if(low<high) { mid=(low+high)/2; mergesort(low,mid); mergesort(mid+1,high); merge(low,high,mid); } ) Merge( low, mid, high) { int h,i,j,k,b[50]; h=low; i=low; j=mid+1; while((h<=mid)&&(j<=high)) { if(A[h]<A[j]) { b[i]=A[h]; h++; }else{ b[i]=A[j]; j++; } i++; } if(h>mid) { for(k=j;k<=high;k++) { b[i]=A[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=A[k]; i++; } } for(k=low;k<=high;k++) { A[k]=b[k]; } }

Coding with c++ :

#include <iostream>

using namespace std;

void MergeSort(int low, int high);

void Merge(int , int , int );

int A[50];

int main()

{

 int i, elemen;

 cout<<"Berapa banyak elemen yang ingin disusun ? "; cin>>elemen;

 cout<<endl;

 cout<<"Masukkan " <<elemen<<" elemen: \n";cout<<endl;

 for(i=1;i<=elemen;i++)

 {

   cout << "Elemen ke-"<<i<<" = ";

   cin>>A[i];

 }

 cout<<endl;

 MergeSort(1,elemen);

 cout<<endl;

 cout<<"Setelah di mergesort: \n\n";

 for(i=1;i<=elemen;i++)

 {

    cout<< A[i] <<" ";

 }

 cout<< endl << endl;

 return 0;

}

//prosedure Mergesort

void MergeSort(int low, int high)

{

 int mid;

 if(low<high)

 {

    mid = (low+high)/2;

    MergeSort(low,mid);

    MergeSort(mid+1, high);

    Merge(low, mid, high);

 }

}

//Prosedure Merge

void Merge(int low, int mid, int high)

{

 int h,i,j,k,b[50];

 h=low;

 i=low;

 j=mid+1;

 while((h<=mid)&&(j<=high))

 {

    if(A[h]<A[j])

    {

       b[i]=A[h];

       h++;

    }else{

       b[i]=A[j];

       j++;

    }

   i++;

 }

 if(h>mid)

 {

    for(k=j;k<=high;k++)

    {

      b[i]=A[k];

      i++;

    }

 }else{

    for(k=h;k<=mid;k++)

    {

      b[i]=A[k];

      i++;

    }

 }

 for(k=low;k<=high;k++)

 {

    A[k]=b[k];

 }

}

Output: