Merge Sort adalah metode dengan menggunakan konsep devide and conquer yang membagi data dalam dua kelompok. Proses pembagian data dilakukan secara rekursif (fungsi yang didalam implementasinya memanggil dirinya sendiri) sampai data tidak dapat dibagi lagi atau dengan kata lain data dalam sub bagian menjadi tunggal. Setelah data tidak dapat dibagi lagi, proses penggabungan (merging) dilakukan antara sub-sub bagian dengan memperhatikan urutan data yang diinginkan baik itu ascending atau descending. Proses penggabungan ini dilakukan sampai semua data tergabung dan terurut sesuai urutan yang diiginkan.
Script:
#include<iostream>
using namespace std;
void merge(int val[], int left, int pivot, int right, char o)
{
int temp[100];
int w, x, y;
w = 0;
x = left;
y = pivot + 1;
if(o == 'A')
{
while((x <= pivot) && (y <= right))
{
if(val[x] <= val[y])
temp[w++] = val[x++];
else
temp[w++] = val[y++];
}
}
else if(o == 'D')
{
while((x <= pivot) && (y <= right))
{
if(val[x] >= val[y])
temp[w++] = val[x++];
else
temp[w++] = val[y++];
}
}
while(x <= pivot)
temp[w++] = val[x++];
while(y <= right)
temp[w++] = val[y++];
for(x = right; x >= left; x--)
{
val[x]=temp[--w];
}
}
void mergesort(int val[], int left, int right, char o)
{
int pivot;
if(left < right)
{
pivot = (left+right) / 2;
mergesort(val, left, pivot, o);
mergesort(val, pivot+1, right, o);
merge(val, left, pivot, right, o);
}
}
int main()
{
char urut;
int nilai[100];
int z, jumlah;
cout<<"Jumlah Data : ";
cin>>jumlah;
cout<<"Urut [A/D] : ";
cin>>urut;
cout<<"--------------------------------\n";
for(z = 0; z < jumlah; z++)
{
cout<<"Nilai ke-"<<1 + z<<" : ";
cin>>nilai[z];
}
mergesort(nilai, 0, jumlah - 1, urut);
cout<<"--------------------------------\n";
cout<<" HASIL SORTIR \n";
cout<<"--------------------------------\n";
for(z = 0; z < jumlah; z++)
{
cout<<nilai[z]<<" ";
}
return 0;
}
No comments:
Post a Comment