Home > Ren's Free Time > Mengurutkan Bilangan pada Array menggunakan Algoritma Merge Sort

Mengurutkan Bilangan pada Array menggunakan Algoritma Merge Sort

November 23, 2010 Leave a comment Go to comments

Algoritma lain yang menggunakan Divide and Conquer dalam pengurutan adalah Merge Sort.

Secara   konseptual,  untuk  sebuah array  berukuran  n,
Merge Sort bekerja sebagai berikut:
1.  Jika  bernilai  0   atau   1,   maka  array  sudah   terurut.

2.   Jika Array tidak terurut, bagi menjadi 2 sub-array dengan ukuran n/2

3. Urutkan setiap sub array. Jika sub array tidak cukup kecil lakukan langkah kedua dengan rekursif

4. Menggabungkan sub array menjadi satu array

Berikut ini implementasi sederhana dari Algoritma Merge Sort dengan C++ dan Tool yang digunakan Code Block 8.02

#include <iostream>

using namespace std;
void merge(int low, int mid, int up);
void mergeSort(int low, int up);
int a[50];
int main()
{
int jumlahBil,i;
cout<<"Masukkan Jumlah element Array"<< endl;
cin>>jumlahBil;
for(int i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << endl;
cin>>a[i];
}
mergeSort(1,jumlahBil);
for(i=1;i<=jumlahBil;i++)
cout<<a[i]<<"    ";
cout<<endl;
return 0;
}
void merge(int low, int mid, int up)
{
int h, i,j,k;
int b[50];
h = low;
i = low;
j = mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h] < a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++){
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=up;k++) a[k]=b[k];
}
void mergeSort(int low, int up)
{

int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}

  1. No comments yet.
  1. December 19, 2013 at 23:52

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: