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

Program C++ Minimal Maksimal Devide and Conquer

Program C++ Minimal Maksimal Devide and Conquer - Pada dasarnya algoritma searching banyak kita jumpai. Apalagi hanya untuk mencari nilai minimum dan nilai maximum.

Pada pembahasan kali ini kita menggunakan algoritma yang sedikit berbeda. Kita tambahkan 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.

Tidak berlama - lama lagi karena yang lama tidak selamanya enak. Langsung saja pada praktek programnya.

Program C++ Minimal Maksimal Devide and Conquer

#include <cstdlib>

#include <iostream>

using namespace std;

void minmax2(int A[], int i, int j, int &min, int &max ){

     /*

     Mencari nilai maksimum dan minimum di dalam tabel A yang 

     berukuran n elemen secara Divide and Conquer.

     Masukan: tabel A yang sudah terdefinisi elemen-elemennya

     Keluaran: nilai maksimum dan nilai minimum tabel

     */

     int min1, min2, max1, max2,k;

     if(i==j){

              min=A[i];

              max=A[i];

              }

     else if(i==j-1){

          if(A[i]<A[j]){

                        max=A[j];

                        min=A[i];

                        }

          else{

               max=A[i];

               min=A[j];

               }

          }

     else{

          k=(i+j)/2;

          minmax2(A,i,k,min1,max1);

          minmax2(A,(k+1),j,min2,max2);

          if(min1<min2)min=min1;

          else min=min2;

          if(max1<max2)max=max2;

          else max=max1;

          }

     }

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

{

    system("color f2");

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

    

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

    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;

    

    minmax2(A,i,j,min,max);

    

    cout<<"\nNilai max = "<<max<<endl;

    cout<<"Nilai min = "<<min<<endl<<endl;

    

    system("PAUSE");

    return EXIT_SUCCESS;

}


Program C++ Minimal Maksimal Devide and Conquer