Bubble dan quick sort
1. Pengertian sorting
Sorting atau pengurutan adalah proses menyusun elemen-elemen dari masukan awal acak, menjadi keluaran akhir yang tertata dengan urutan tertentu. Permasalahan pengurutan (sorting problem) secara formal didefinisikan sebagai berikut . Input di sini adalah uatu urutan dari n bilangan. Output di sini adalah suatu permutasi atau penyusunan kembali dari input sedemikian rupa sehingga pada tata urutan ascending (dari nilai kecil ke besar) atau pada tata urutan descending (dari nilai besar ke kecil). Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan.
Beberapa metode sorting mengurutkan data yang dikenal antara lain adalah :
1. Bubble Sort (sederhana tetapi lambat)
2. Quick Sort (cepat tetapi rumit)
3. Shell Sort (agak cepat dan tidak terlalu rumit)
4. Selection Sort
5. Insert Sort
6. Merge Sort
2. Bubble sort dan quick sort
Bubble Sort (metode gelembung) adalah metode pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus hingga dapat dipastikan dalam suatu kumpulan data, tidak ada lagi perubahan. Jika tidak ada perubahan, berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci, dengan lambat akan menggelembung ke posisinya yang tepat.
Bubble sort memiliki algoritma yang beroperasi seperti berikut.
1. elemen pertama dibandingkan dengan elemen kedua. Bila elemen kedua < elemen pertama, kedua elemen tersebut ditukar.
2. Elemen kedua dan ketiga dibandingkan, bila elemen ketiga < elemen kedua, kedua elemen tersebut ditukar.
3. Proses terus berlangsung dengan elemen ketiga dan keempat, dan seterusnya. Sampai akhir deretan jumlah data, tercapai.
4. Bila tak ada lagi yang ditukarkan, algoritma berhenti.
5. Bila terjadi pertukaran selama berurutan, proses akan diulang. Sehingga semua elemen tersusun, dan tidak ada pertukaran lagi, kemudian algoritma berhenti
Algoritma bubble sort adalah sebagai berikut.
1. Membandingkan data ke-i dengan data ke-(i+1). Jika tidak sesuai, maka tukar data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i. Jika kita menginginkan algoritma 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).
2. 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.
3. 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.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.
kelebihan dan kelemahan bubble sort.
Kelebihan :
1. Merupakan metode sorting yang paling simple.
2. Metode yang mudah dipahami algoritmanya.
Kelemahan :
1. Metode yang paling tidak efisien.
2. Saat mengurutkan data dengan jumlah yang sangat besar, akan mengalami kelambatan.
3. Kinerja memburuk secara signifikan.
4. Jumlah dari pengulangannya akan tetap sama, walaupun data sudah cukup terurut.
Hal-hal ini disebabkan, karena setiap data harus dibandingkan dengan setiap data yang lain untuk menentukan posisinya
Quick Sort, quick sort adalah algoritma pengurutan yang sangat cepat dengan tipe penyelesaian divide and conquer. sehingga cocok untuk mengurutkan data dalam jumlah besar. Ketika proses pengurutan dilakukan secara berulang, maka menghasilkan partisi hanya satu elemen saja dan kemudian digabung kembali sehingga terlihat bahwa data telah berurutan. Strategi divide-and-conqueror digunakan di dalam quicksort.
Di bawah ini akan dijelaskan langkah-langkahnya :
1. Pilih nilai pivot. Kita ambil nilai di tengah-tengah elemen sebagai sebagai nilai dari
pivot, tetapi bisa nilai mana saja.
2. Partisi. Atur ulang semua elemen sedemikian rupa, lalu semua elemen yang lebih rendah daripada pivot dipindahkan ke sebelah kiri dari array/list dan semua elemen yang lebih besar dari pivot dipindahkan ke sebelah kanan dari array/list. Nilai yang sama dengan pivot dapat diletakkan di mana saja dari array.
3. Urutkan semua bagian (kiri dan kanan). Aplikasikan algoritma quick sort secara rekursif pada bagian sebelah kiri dan kanan.
Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat. Quick sort disebut juga dengan partition exchange sort, karena konsepnya membuat partisi- partisi, dan sorting dilakukan per partisi.
Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.
Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma berjalan dengan baik atau tidak. Berikut beberapa cara pemilihan pivot :
1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah array. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut.
2. Pivot dipilih secara acak dari salah satu elemen array. Cara ini baik, tetapi belum tentu maksimal, sebab memerlukan prosedur khusus untuk menentukan pivot secara acak.
3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang. Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.
Kompleksitas Algoritma Quick Sort
Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai pivot. Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian masalah-masalah di dalamnya.
Terdapat 3 jenis kompleksitas waktu dari quick sort :
Kasus terburuk (worst case), yaitu terjadi bila terbentuk partisi dengan komposisi sub-masalah antara n – 1 elemen dan 0 elemen. Dengan demikian pemanggilan fungsi secara rekursif dengan array berukuran 0 akan langsung kembali, T(0) = Θ(1), sehingga berlaku : T(n) = T(n – 1) + cn = O(n2).
Kasus terbaik (best case), yaitu terjadi bila terbentuk partisi dengan dengan komposisi seimbang, dengan ukuran masing-masing tidak lebih dari n/2. Sehingga didapat: T(n) = 2T(n/2) + cn = na + cn log n = O(n log n).
Kasus rata-rata (average case), yaitu terjadi dari perimbangan pivot antara terbaik dan terburuk, yang dalam prakteknya lebih mendekati kasus terbaik ketimbang terburuk. Sehingga didapat: Tavg(n) = O(n log n).
Kelebihan dan Kelemahan Algoritma Quick Sort
Beberapa hal yang membuat quick sort unggul :
1. Secara umum memiliki kompleksitas O(n log n).
2. Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
3. Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.
4. Melakukan proses langsung pada input.
5. Bekerja dengan baik pada berbagai jenis input data seperti angka dan karakter.
Namun terdapat pula kelemahan quick sort :
1. Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan, hasilnya tidak benar atau tidak pernah selesai.
2. Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).
3. Secara umum bersifat tidak stabil, yaitu mengubah urutan input dalam hasil akhirnya, dalam hal input yang memiliki nilai sama.
4. Pada penerapan secara rekursif atau memanggil dirinya sendiri, bila terjadi kasus terburuk dapat menghabiskan stack dan memberhentikan program.
3. Algoritma bubble sort dan quick sort
1. Algoritma bubble sort adalah sebagai berikut.
for(i=0;
i<=n-2; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (data[j]<data[j-1])
{
buble=data[j];
data[j]=data[j-1];
data[j-1]=buble;
}
}
}
2. Algoritma quick sort adalah sebagai berikut.
1. Quick sort, I=left, j=right.
Pivot
= data[tengah] = data[left+right/2]
2. Ketentuan partisi
I
< j
Data[i]
< pivot = i++
Data[j]
< pivot = j—
I
≤= j = data[i] ↔ data[j]
I++,
j--
3. Rekursif
Left
< j = quick sort (data, left, j)I < right = quick sort (data, I, right)
4. Contoh program
1. Berikut contoh program bubble sorting.
#include
<iostream>
using namespace
std;
int main()
{
int i,j,n, buble, pilih,
data[10],input[10];
string pil;
cout<<" PROGRAM SORTING "<<endl;
cout<<" Pilih Metode : "<<endl;
cout<<" 1. Ascending "<<endl;
cout<<" 2. Descending "<<endl;
cout<<endl;
cout<<"Masukkan jumlah data yang
ingin di simpan : ";cin>>n;
for(i=0; i<n; i++)
{
cout<<"Data ke -
"<<i+1<<" : ";cin>>data[i];
}
atas:
cout<<"Masukkan metode yang
ingin digunakan : ";cin>>pilih;
if (pilih==1)
{
for(i=0; i<=n-2; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (data[j]<data[j-1])
{
buble=data[j];
data[j]=data[j-1];
data[j-1]=buble;
}
}
}
cout<<"Data telah disorting
secara ascending "<<endl;
for(i=0; i<n; i++)
{
cout<<"Data ke -
"<<i+1<<" : "<<data[i]<<endl;
}
}
else if (pilih==2)
{
for(i=0; i<=n-2; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (data[j]>data[j-1])
{
buble=data[j];
data[j]=data[j-1];
data[j-1]=buble;
}
}
}
cout<<"Data telah disorting
secara descending "<<endl;
for(i=0; i<n; i++)
{
cout<<"Data ke -
"<<i+1<<" : "<<data[i]<<endl;
}
}
else
{
cout<<"Pilihan salah.
Apakah anda ingin mengulang [Y/T] : ";cin>>pil;
cout<<endl;
if(pil=="y"||pil=="Y")
{
goto atas;
}
else
if(pil=="t"||pil=="T")
{
cout<<"Proses
selesai"<<endl;
}
}
}
Hasil running dari program di atas adalah sebagai berikut.
a. Hasil running program dengan data ascending
b. Hasil running program dengan data descending
2. Berikut contoh program quick sorting.
#include
<iostream>
#include
<conio.h>
using
namespace std;
void
quick_sort(int arr[], int left, int right)
{
int i = left, j = right;int tmp;
int pivot = arr[(left+right)/2];/*
partition */
while (i<j){
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i<=j){
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;j--;
};
}; /* recursion */
if (left < j)
quick_sort(arr, left, j);
if (i < right)
quick_sort(arr, i, right);
}
int
main()
{
int
i,n,data[50];
cout<<"Masukan
banyak data: ";cin>>n;
for(i=0;i<n;i++)
{cout<<"Masukan
data ["<<i<<"] : ";cin>>data[i];}
cout<<"\nData
sebelum diurutkan: "<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<"
";
}cout<<"\n";
quick_sort(data,0,n-1);//hasil
pengurutan
cout<<"\nHasil
pengurutan:\n";
{
int
i;
for
(i=0;i<n;i++)
cout<<data[i]<<"
";
cout<<"\n";
}getch();
}
Hasil running dari program di atas adalah sebagai berikut.
Referensi :
https://www.academia.edu/10450333/Laporan_Quick_Sort
http://dtugasalgoritma.blogspot.com/2010/12/quick-sort-algoritma.html
http://onophp.blogspot.com/2018/11/quick-sort-pengertian-agoritma-dan.html
http://www.pintarkoding.com/metode-pemograman-algoritma-quick-sort/
