Merge sort merupakan salah satu metode sorting yang paling stabil, kompleksitas nya juga O(n log n) untuk kasus terburuk dan terbaik sekalipun.
Merge sort menggunakan metode Divide and Conquer untuk menyelesaikan penyusunannya, jadi data akan di pecah - pecah menjadi sangat kecil dan di selesaikan satu per satu.
Ini ada suatu gambar yang saya dapatkan dari wikipedia, cukup untuk membuat kita mudah mengerti maksud dari sorting ini.
Sudah bisa mengerti gambar ini ??
Lalu bagaimana mengimplementasikan dalam sebuah program ?
Silahkan cek source code yang saya buat dengan C++
#include <iostream>
using namespace std;
int data[100];
void mergeSort(int awal, int mid, int akhir)
{
cout<<endl;
int temp[100], tempAwal = awal, tempMid = mid, i = 0;
while(tempAwal < mid && tempMid < akhir)
{
if(data[tempAwal] < data[tempMid])
temp[i] = data[tempAwal],tempAwal++;
else
temp[i] = data[tempMid],tempMid++;
i++;
}
while(tempAwal < mid) //kalau masih ada yang sisa
temp[i] = data[tempAwal],tempAwal++,i++;
while(tempMid < akhir)
temp[i] = data[tempMid],tempMid++,i++;
for(int j=0,k=awal;j<i,k<akhir;j++,k++) //mengembalikan ke array semula, tapi
cout<<data[k]<<' '<<temp[j]<<endl, data[k] = temp[j]; //sudah urut
}
void merge(int awal, int akhir) //membagi data secara rekursif
{
if(akhir-awal != 1)
{
int mid = (awal+akhir)/2;
merge(awal, mid);
merge(mid, akhir);
mergeSort(awal, mid, akhir);
}
}
int main()
{
int n;
cout<<"Masukan banya data = ";cin>>n;
cout<<"Masukan data yang akan di susun = ";
for(int i=0;i<n;i++)
cin>>data[i];
merge(0,n);
for(int i=0;i<n;i++)
cout<<data[i]<<' ';
return 0;
}
Rabu, 24 November 2010
Merge Sort
Langganan:
Posting Komentar (Atom)
nice job.....!
BalasHapus