Program C++ Merge Sort Devide and Conquer

Program C++ Merge Sort Devide and Conquer - Pada Algoritma pencarian banyak yang bisa kita temukan atau gunakan. Ada Merge Sort, Quick Sort, Bubble Sort, dan masih banyak lagi.

Pada kesempatan kali ini kita akan fokus membahas masalah Merge Sort. Tetapi disini kita akan menambahkan algoritma Devide and Conquer.

Algoritma Devide and Conquer secara singkat adalah algoritma pemecahan masalah menjadi lebih kecil. Shingga permasalahan akan lebih mudah dan cepat untuk diselesaikan.

Sekarang kita langsung menuju program untuk memecahkan masalah pencarian dengan Merge Sort secara Devide and Conquer.

Program C++ Merge Sort Devide and Conquer

#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.

*/

int B[100];

int i, kidal1, kidal2;

kidal1=kiri;// { A[kiri .. tengah] }

kidal2=tengah + 1;//   { A[tengah+1 .. kanan] }

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 (i=kiri;i<=kanan;i++){

  A[i]=B[i];

    }   

   //{ diperoleh tabel A yang terurut membesar }

}

void MergeSort(int A[], int i, int j){

/* Mengurutkan tabel A[i..j] dengan algoritma Merge Sort 

  Masukan: Tabel A dengan n elemen

  Keluaran: Tabel A yang terurut

*/

int k;

   if (i < j){// { Ukuran(A)> 1}

     k=(i+j)/2;

     MergeSort(A, i, k);

     MergeSort(A, k+1, j);

     merge(A, i, k, j);

   }

}

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

{

    system("color f2");

    system("title MergeSort - Selasa, 29 Mei 2012 - dyasprogramming.blogspot.com");

    

    int A[100],n,i,j;

    cout<<"Mauskkan banyak data : ";

    cin>>n;

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

            cout<<"Data ke-"<<a<<" : "; //Masukan data sebanyak n elemen

            cin>>A[a];

            }

    i=1;

    j=n;

    

    MergeSort(A,i,j);

    

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

            cout<<A[a]<<" ";

            }

    

   system("PAUSE");

    return EXIT_SUCCESS;

}

Program C++ Merge Sort Devide and Conquer