SORTING
Sorting
adalah suatu proses mengatur sekumpulan objek menurut aturan atau susunan
tertentu. Urutan objek tersebut dapat menaik atau disebut juga ascending (dari data kecil ke data lebih
besar) ataupun menurun atau disebut descending
(dari data besar ke data kecil).
Metode
sorting yang sering digunakan terdapat enam jenis, yaitu:
1.
Bubble
Sort
2.
Quick
Sort
3.
Merge
Sort
4.
Insertion
Sort
5.
Selection
Sort
6.
Shell
Sort
1. BUBBLE SORT
Bubble sort merupakan algoritma pengurutan paling tua dengan
metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan
membandingkan masing-masing item dalam
suatu list secara berpasangan, menukar item jika
diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak
ada lagi item yang dapat ditukar.
Ada Beberapa Yang Perlu Diketahui
Mengenai Bubble Sort:
1. Metode sorting termudah
2. Diberi Nama “Bubble” karena proses
pengurutan secara berangsur-angsur bergerak atau berpindah ke posisinya yang
tepat, seperti gelembung yang keluar dari sebuah gelas bersoda.
3. Bubble Sort mengurutkan data dengan
cara membandingkan elemen sekarang dengan elemen berikutnya.
4. Jika elemen sekarang lebih besar dari
elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending.
5. Jika Elemen Sekarang Lebih Kecil Dari
Elemen Berikutnya, Maka Kedua Elemen Tersebut Ditukar, Jika Pengurutan
Descending.
6. Algoritma Ini Seolah-Olah Menggeser
Satu Per Satu Elemen Dari Kanan Ke Kiri Atau Kiri Ke Kanan, Tergantung Jenis
Pengurutannya.
7. Ketika Satu Proses Telah Selesai,
Maka Bubble Sort Akan Mengulangi Proses, Demikian Seterusnya.
8. Kapan Berhentinya? Bubble Sort
Berhenti Jika Seluruh Array Telah Diperiksa Dan Tidak Ada Pertukaran Lagi Yang
Bisa Dilakukan, Serta Tercapai Perurutan Yang Telah Diinginkan.
Kelebihan Bubble Sort:
1. Metode
Buble Sort merupakan metode yang paling simple.
2. Metode
Buble Sort mudah dipahami algoritmanya.
3. Mudah
untuk diubah menjadi kode.
4. Definisi
terurut terdapat dengan jelas dalam algoritma.
5. Cocok
untuk pengurutan data dengan elemen kecil telah terurut.
Kelemahan Bubble Sort:
1. Bubble
Sort merupakan metode pengurutan yang paling tidak efisien.
2. 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.
Contoh Program:
#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:
#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:
#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:
Pero kali abang
ReplyDelete