Buble adalah metode pengurutan paling simpel (menurut saya), mengecek apakah ada yang lebih besar atau tidak, lalu di tukar, tapi dengan kasus terburuk kompleksitasnya mencapai O(N2).
Ini ada contoh source code C++ saya
#include <iostream>
using namespace std;
int main()
{
int data[100],n;
cout<<"Berapa banyak data = ";cin>>n;
cout<<"Masukan data yang akan di sorting = ";
for(int i=0;i<n;i++)
cin>>data[i];
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
if(data[i] > data[j])
swap(data[i],data[j]);
for(int i=0;i<n;i++)
cout<<data[i]<<' ';
return 0;
}
Read More...
Rabu, 24 November 2010
Buble Sort
Merge Sort
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;
}
Read More...