Algoritma Merge Sort

Ada banyak cara atau metode untuk melakukan Sorting (pengurutan) salah satunya yang akan di bahas di blog ini adalah MergeSort.

Untuk mengurutkan beberapa elemen, Merge Sort mengggunakan teknik Divide and Conquer  yang tahapan-tahapannya sbb :)  :

Tahapan-tahapannya:

1. Tahap Divide

Array A dibagi menjadi 2 bagian array , yaitu A1 dan A2. Kalau pembagiannya masih terlalu besar maka masing-masing bagian tadi dibagi menjadi dua bagian lainnya menjadi lebih kecil.

2. Tahap Recursion

Masing-masing bagian diurutkan dengan cara rekursif.

3. Tahap Conquer

Setelah diurutkan, masing-masing bagian array  digabungkan dan diurutkan sehingga menjadi satu array (Array A) yang utuh dan telah disusun secara urut🙂

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];

 }

 }

Nah sekarang kita coba coding with c++:mrgreen:


#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];

 }

}

Outputnya🙂

3 Responses to “Algoritma Merge Sort”


  1. 1 heru768 Desember 19, 2009 pukul 5:22 am

    bagus blognya….
    maen2 ke blog saya….

  2. 2 Reza Fahmi Juni 19, 2014 pukul 4:43 am

    Bagaimana klau input datanya 10,
    sya msh kurang jlas.
    Mhon bantuannya.


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




Me (^^)

About

Blog ini adalah catatan kuliah ku, tidak hanya mengenai materi kuliah tetapi juga tentang kegiatan, pengalaman aku selama kuliah :) .


=-=-=-=-=
image header = "Byousoku 5 cm " with edited :)

Liroesdy on Net (=^_^=)

Blog Stats

  • 59,078 hits
Click to view my 

Personality Profile page

My Personal Blog

Liroesdy Blog

Liroesdy Lab

Liroesdy Lab

%d blogger menyukai ini: