Pengertian Sorting
Pengurutan (Sorting) merupakan proses pengurutan sekumpulan data dalam suatu urutan tertentu.
Sorting dipakai untuk:
1. Membantu proses pencarian (searching)
2. Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.
1. Membantu proses pencarian (searching)
2. Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.
Jenis-Jenis Sorting
1. BUBBLE SORT
Bubble Sort (metode gelembung) adalah metode pengurutan dengan cara
melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai
bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika
tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung
karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang
tepat.
Kelebihan
dan Kekurangan Bubble Sort
-
Kelebihan:
1) Metode Bubble Sort merupakan yang paling simple.
2) Metode Bubble Sort mudah dipahami algoritmanya.
1) Metode Bubble Sort merupakan yang paling simple.
2) Metode Bubble Sort mudah dipahami algoritmanya.
-
Kelemahan:
Meskipun simpel metode Bubble Sort merupakan metode pengurutan yang paling tidak efisien. Kelemahan Bubble Sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.
Meskipun simpel metode Bubble Sort merupakan metode pengurutan yang paling tidak efisien. Kelemahan Bubble Sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.
Algoritma dari Bubble Sort
·
Membandingkan data ke-i dengan data
ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data
ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita
menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi
tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan
descending (A-Z).
·
Membandingkan data ke-(i+1) dengan
data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1
dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
·
Selesai satu iterasi, adalah jika
kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu
iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai
dari data ke-1 dgn data ke-2, dan seterusnya.
·
Proses akan berhenti jika tidak ada
pertukaran dalam satu iterasi
Contoh Program Bubble Sort:
|
#include <iostream>
#include <conio.h>
using namespace std;
main()
{
int nilai['n'];
int temp;
int n;
cout<<"Masukkan Banyak Data:
"; cin>>n;
cout<<endl;
for (int a=1; a<=n; a++)
{
cout<<"Nilai["<<a<<"]: ";
cin>>nilai[a];
}
cout<<"\n";
cout<<"Data Sebelum
Diurutkan"<<endl;
for(int a=1; a<=n; a++)
{
cout<<nilai[a]<<"
";
}
for(int a=n-1; a>=1; a--)
{
for(int b=1; b<=a; b++)
{
if(nilai[b]>nilai[b+1])
{
temp=nilai[b+1];
nilai[b+1]=nilai[b];
nilai[b]=temp;
}
}
}
cout<<"\n\nData Setelah
Diurutkan (Ascending)"<<endl;
for (int a=1; a<=n; a++)
{
cout<<nilai[a]<<"
";
}
cout<<"\n\nData Setelah
Diurutkan (Descending)"<<endl;
for (int a=n; a>=1; a--)
{
cout<<nilai[a]<<"
";
}
getch();
}
|
Output:
2. QUICK
SORT
Algoritma Quick Sort
ini berdasar pada pola divide and conquer.
Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah
sebagai berikut:
1. Divide
1. Divide
Memilah
rangkaian data menjadi dua sub rangkaian A[p…q-1] dan A[q+1…r] dimana setiap
elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada
A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut
sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian
dari prosedur pemisahan.
2.
Conquer
Mengurutkan
elemen pada sub rangkaian secara rekursif. Pada algoritma Quick Short, langkah
”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen
pada sub-array.
Kelebihan:
Algoritma
Quick Sort memiliki kompleksitas
O(nlogn) dimana pada prakteknya lebih cepat dari algoritma pengurutan lainnya.
Kekurangan:
Pada
kemungkinan terburuknya, algoritma Quick
Sort ini dapat memiliki kompleksitas O(n2). Meskipun ini sangat langka
terjadi.
Contoh program quick sort:
|
#include
<iostream>
#include
<conio.h>
using namespace
std;
void
tampilkan_data(int data[], int n)
{
int i;
for (i=1;i<=n;i++)
cout<<data[i]<<"
";
cout<<"\n";
}
int partisi (int
data[], int awal, int akhir)
{
int x,i,j,simpan;
i=awal;
j=akhir;
while(1)
{
while(data[i]<data[awal])
i=i+1;
while(data[j]>data[awal])
j=j-1;
if (i<j)
{
simpan=data[i];
data[i]=data[j];
data[j]=simpan;
}
else
return j;
}
}
void
quick_sort(int data[], int awal, int akhir)
{
int q;
if(awal<akhir)
{
q=partisi(data,awal,akhir);
quick_sort(data,awal,q);
quick_sort(data, q+1,akhir);
}
}
int main()
{
int i,j,n,data[100];
cout<<"Masukkan Banyak Data:
";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"\nData
Ke-"<<i<<" = ";cin>>data[i];
}
cout<<"\nData Sebelum
Diurutkan: "<<endl;
for(j=1;j<=n;j++)
{
cout<<data[j]<<"
";
}
quick_sort(data,1,n);
cout<<endl<<endl;
cout<<"Data Hasil
Pengurutan:\n";
tampilkan_data(data,n);
getch();
}
|
Output:
3. MERGE SORT
Merge
Sort merupakan pengurutan untuk data yang jumlahnya besar, dimana data tidak semuanya
dapat dimuat dalam memori utama (main memory), sehingga harus disimpan dalam
penyimpanan sekunder (secondary storage)
berupa berkas (file). Proses
penggabungan sedikitnya dua buah file ke dalam file lain dalam kondisi
terurut. Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer.
Berikut menjelaskan langkah kerja dari Merge Sort:
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif.
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan. Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan. Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Konsep dari Merge Sort
sendiri adalah sebagai berikut:
1. Bagi list besar menjadi setengahnya
1. Bagi list besar menjadi setengahnya
2. Lakukan hal ini secara rekursif
sampai diperoleh list dengan satu elemen saja
3. List tersebut digabung lagi
menjadi sebuah list besar yang sudah terurut.
Kelebihan dari Merge
Sort:
Dibanding dengan algoritma lain, merge sort ini termasuk algoritma yang
sangat efisien dalam penggunaannya sebab setiap list selalu dibagi bagi menjadi
list yang lebih kecil, kemudian digabungkan lagi.
Contoh Program Merge Sort:
|
#include <iostream>
#include <conio.h>
using namespace std;
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
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];
}
main()
{
int num,i;
cout<<"Masukkan Banyak Bilangan:
";cin>>num;
cout<<endl;
cout<<"Masukkan "<<
num <<" Bilangan Yang Akan Diurutkan:"<<endl;
for(i=1;i<=num;i++)
{
cout<<"Bilangan ke-"<<i<<" :
";cin>>a[i] ;
}
merge_sort(1,num);
cout<<endl;
cout<<"Data Hasil Pengurutan:
"<<endl;
cout<<endl;
for(i=1;i<=num;i++)
cout<<a[i]<<" ";
cout<<endl;
getch();
}
|
Output:
Komentar
Posting Komentar