Program Merge Sort dengan Algoritma Divide and Conquer

Selamat malam omnivora (hahahahahahaha)


Kembali Posting mengenai Algoritma Divide and Conquer. kali ini saya mencontohkan program Merge Sort n buah data, langsung saja saya jelaskan di bawah ini:

Divide:  membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara  rekursif), dan

Combine: menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula. 
 
 Algoritmanaya :

procedure MergeSort(input/output A : TabelInt,   input i, j : integer) { Mengurutkan tabel A[i..j] dengan algoritma    Merge Sort Masukan: Tabel A dengan n elemen   Keluaran: Tabel A yang terurut } Deklarasi:    k : integer Algoritma:    if i < j then  { Ukuran(A)> 1}      k¬(i+j) div 2      MergeSort(A, i, k)      MergeSort(A, k+1, j)      Merge(A, i, k, j)    endif

procedure Merge(input/output A : TabelInt, input kiri, tengah,kanan : integer) { Menggabung tabel A[kiri..tengah] dan tabel    A[tengah+1..kanan]   menjadi tabel A[kiri..kanan] yang terurut menaik.   Masukan: A[kiri..tengah] dan tabel A[tengah+1..kanan]    yang sudah terurut menaik.   Keluaran: A[kiri..kanan] yang terurut menaik. } Deklarasi B : TabelInt i, kidal1, kidal2 : integer Algoritma: kidal1¬kiri { A[kiri .. tengah] } kidal2¬tengah + 1   { A[tengah+1 .. kanan] } i¬kiri while (kidal1 £ tengah) and (kidal2 £ kanan) do         if Akidal1 £ Akidal2 then         Bi¬Akidal1    kidal1¬kidal1 + 1     else         Bi¬Akidal2    kidal2¬kidal2 + 1    endif    i¬i + 1     endwhile  { kidal1 > tengah or kidal2 > kanan } { salin sisa A bagian kiri ke B, jika ada } while (kidal1 £ tengah) do         Bi¬Akidal1    kidal1¬kidal1 + 1    i¬i + 1     endwhile    { kidal1 > tengah }    { salin sisa A bagian kanan ke B, jika ada } while (kidal2 £ kanan) do     Bi¬Akidal2    kidal2¬kidal2 + 1    i¬i + 1 endwhile  { kidal2 > kanan }    { salin kembali elemen-elemen tabel B ke A } for i¬kiri to kanan do    Ai¬Bi     endfor       { diperoleh tabel A yang terurut membesar }

Implementasi ke dalam Bahasa Pemrograman C++

#include <cstdlib>

#include <iostream>

using namespace std;

void Merge(int* A, int kiri,int tengah, int kanan){

int B[kiri+kanan];

int i,kidal1,kidal2;

kidal1=kiri;

kidal2=tengah+1;

i=kiri;

while (kidal1<=tengah && kidal2 <= kanan){

if(A[kidal1] <= A[kidal2]){

B[i]=A[kidal1];

kidal1++;

}

else{

B[i]=A[kidal2];

kidal2++;

}

i++;

}

    while ( kidal1 <= tengah ){

        B[i] = A[kidal1];

        kidal1++;

        i++;

        }

    while ( kidal2 <= kanan ){

        B[i] = A[kidal2];

        kidal2++;

        i++;

        }

for (int i=kiri;i<= kanan;i++){

A[i]=B[i];

}

}

void MergeSort (int* A, int i, int j){

int k;

if (i<j){

k= ((i+j)/2);

MergeSort(A, i, k);

MergeSort(A, k+1, j);

Merge(A, i, k, j);

}

}

int main(int argc, char *argv[])

{

int n;

int i;

int j;

cout<<"Merge Sort with Divide and Conquer Algoritm";

cout<<"Banyak data :";

cin>>n;

i=1;

j=n;

int A[n];

for (int x=1;x<=n;x++){

cout<<"masukan data ke-"<<x<<" : ";

cin>>A[x];

}

cout<<"Data sebelum diurutkan "<<endl;

for (int x=1;x<=j;x++){

cout<<A[x]<<" ";

    }

    cout<<endl;

MergeSort(A,i,j);

cout<<"Data setelah diurutkan "<<endl;

for (int x=1;x<=j;x++){

cout<<A[x]<<" ";

    }

    cout<<endl;

system("pause");

return 0;

}

hasil Running

 

Sekian......
Semoga bermanfaat untuk anda,
Terima kritik dan saran untuk pengembangan

Source Code dapat di download disini