Merge Sort

Posted: 11 Mei 2014 in Strategi Algoritma

Algoritma Divide and Conquer

yakni sebuah algoritma yang memiliki 3 bagian, yaitu :

1. Divide : membagi masalah menjadi bagian yang lebih kecil.

2. Conquer : memecah masalah secara rekursif atau berulang-ulang.

3. Combine : menggabungkan masalah menjadi satu lagi.

 

Nah, kali ini saya akan berbagi mengenai MergeSort :

Bagian I : Ketahui dahulu algoritmanya 

 

 

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

 

 

Prosedur Merge:

 

 

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 }

 

 Setelah tahu algoritma nya , selanjutnya implementasikan ke c++, sebagai berikut :

#include <cstdlib>
#include <iostream>

using namespace std;

void Merge(int* A, int kiri,int tengah, int kanan){
/*{ 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
int B[kiri+kanan];
int i,kidal1,kidal2;

//Algoritma
kidal1=kiri;
kidal2=tengah+1;
i=kiri;

while (kidal1<=tengah && kidal2 <= kanan){
if(A[kidal1] <= A[kidal2]){
B[i]=A[kidal1];
kidal1=kidal1 + 1;
}
else {
B[i]=A[kidal2];
kidal2=kidal2 + 1;
}
i=i + 1;
}
//{ kidal1 > tengah or kidal2 > kanan }

//{ salin sisa A bagian kiri ke B, jika ada }
while ( kidal1 <= tengah ){
B[i] = A[kidal1];
kidal1=kidal1 + 1;
i=i + 1;
}
//{ kidal1 > tengah }

//{ salin sisa A bagian kanan ke B, jika ada }
while ( kidal2 <= kanan ){
B[i] = A[kidal2];
kidal2=kidal2 + 1;
i=i + 1;
}
//{ kidal2 > kanan }

//{ salin kembali elemen-elemen tabel B ke A }
for (int i=kiri;i<= kanan;i++){
A[i]=B[i];
}
//{ diperoleh tabel A yang terurut membesar }
}

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”;
cout<<endl;
cout<<endl;
cout<<“masukkan jumlah 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<<endl;
cout<<endl;
cout<<“Data asli sebelum di merge sort “;
cout<<endl;

for (int x=1;x<=j;x++){
cout<<A[x]<<“\t”;
}
cout<<endl;
cout<<endl;
cout<<“Data setelah di merge sort “;
cout<<endl;

MergeSort(A,i,j);
for (int x=1;x<=j;x++){
cout<<A[x]<<“\t”;
}
cout<<endl;

system(“pause”);
return 0;
}

Schreenshotnya akan jadi seperti ini :

Gambar

Selamat mencoba,😳

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s