Quick Sort
Algoritma
quick sort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960. Quick
sort adalah algoritma sorting yang berdasarkan pembandingan dengan metode divide and conquer (bagi dan kuasai).
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.
Pivot
Dalam
algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah
algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. 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.
Contoh
:
Pada
array dengan data :
6
|
2
|
9
|
5
|
4
|
1
|
7
|
3
|
8
|
Pada
data tersebut akan di urutkan menggunakan metode quick sort , pada contoh akan
menggunakan pivot dari titik tengah pada array menggunakan aritmatika :
pivot
= (x+y)/2
pivot
= (0+8)/2 = 4
·
pivotnya berada pada indeks ke-4 yaitu = 4
·
pada data awal x = adalah nilai paling
kiri dalam indeks array yaitu ( 0 ), x akan memindai data dari sebelah kiri dan
akan mencari data yang lebih besar / sama dengan pivot, jika x menemukan data
yang lebih kecil dari pivot maka x akan bergeser ke kanan (x+1).
·
pada data awal y = adalah nilai paling kanan
dalam indeks array yaitu ( 8 ),y akan memindai data dari sebelah kanan dan
mencari data yang lebih kecil / sama dengan pivot, jika y menemukan data yang
lebih besar dari pivot maka y akan bergeser ke kiri (y-1).
·
Jika x dan y menemukan data yang sesuai
dengan syarat diatas maka posisi dari data tersebut akan ditukar .
Indeks
:
[0] [1] [2] [3] [4] [5] [6] [7] [8]
6
|
2
|
9
|
5
|
4
|
1
|
7
|
3
|
8
|
x y
Langkah
1: (data x > pivot) maka x berhenti pada indeks[0], (data y > pivot) maka
y akan berjalan kekiri (y-1).
6
|
2
|
9
|
5
|
4
|
1
|
7
|
3
|
8
|
x y
Langkah
2: x tetap pada indeks[0], (data y < pivot) maka y berhenti pada indeks[7]
dan syarat terpenuhi maka data pada indeks [0] dan [7] ditukar, setelah posisi
ditukar maka x bergeser ke kanan (x+1) dan y bergeser ke kiri (y-1).
3
|
2
|
9
|
5
|
4
|
1
|
7
|
6
|
8
|
x y
Langkah
3: (data x < pivot) maka x bergeser ke kiri (x+1), (data y > pivot) maka
y akan bergeser ke kanan (y-1).
3
|
2
|
9
|
5
|
4
|
1
|
7
|
6
|
8
|
x y
Langkah
4: (data x > pivot) maka x berhenti pada indeks[2], (data y < pivot) maka
y berhenti pada indeks[5] dan syarat terpenuhi maka data pada indeks [2] dan [5]
ditukar, setelah posisi ditukar maka x bergeser ke kanan (x+1) dan y bergeser
ke kiri (y-1).
3
|
2
|
1
|
5
|
4
|
9
|
7
|
6
|
8
|
x y
Langkah
5: (data x > pivot) maka x berhenti pada indeks [3], (data y = pivot) maka y
berhenti pada indeks[4] dan syarat terpenuhi maka data pada indeks [3] dan [4]
ditukar, setelah posisi ditukar maka x bergeser ke kanan (x+1) dan y bergeser
ke kiri (y-1).
3
|
2
|
1
|
4
|
5
|
9
|
7
|
6
|
8
|
y x
karena
x > y maka pembagian partisi telah selesai dan array menjadi 2 bagian,
seperti di bawah ini bagian kiri dari pivot akan berisi data yang lebih kecil
dan sebelah kanan pivot akan berisi data yang lebih besar.
Maka
sorting akan diteruskan dengan masing-masing partisi, yaitu partisi kiri terlebih
dahulu dan kemudian partisi kanan.
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3
|
2
|
1
|
4
|
5
|
9
|
7
|
6
|
8
|
3
|
2
|
1
|
x y
Langkah
6: pivot pada partisi kiri adalah (0+2)/2=1 maka pivotnya berada pada indeks[1]
= 2, maka di cek (data x > pivot) maka x tetap pada indeks[0], (data y <
pivot) dan syarat terpenuhi maka data pada indeks [0] dan [2] ditukar, setelah
posisi ditukar maka x bergeser ke kanan (x+1=1) dan y bergeser ke kiri (y-1=1).
1
|
2
|
3
|
Maka
nilai x=y dan sorting untuk partisi kiri selesai, maka akan dilanjutkan dengan
partisi kanan.
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3
|
2
|
1
|
4
|
5
|
9
|
7
|
6
|
8
|
5
|
9
|
7
|
6
|
8
|
x y
Langkah
7: pivot pada partisi kiri adalah (4+8)/2=6 maka pivotnya berada pada indeks[6]
= 7, maka di cek (data x < pivot) maka x bergeser ke kanan (x+1), (data y
> pivot) maka y bergeser ke kiri (y-1).
[4] [5] [6] [7] [8]
5
|
9
|
7
|
6
|
8
|
x y
Langkah
8: (data x > pivot) maka x berhenti pada indeks [5], (data y = pivot) maka y
berhenti pada indeks[7] dan syarat terpenuhi maka data pada indeks [5] dan [7]
ditukar, setelah posisi ditukar maka x bergeser ke kanan (x+1=6) dan y bergeser
ke kiri (y-1=6).
[4] [5] [6] [7] [8]
5
|
6
|
7
|
9
|
8
|
Maka x=y maka sorting pada partisi
kanan selesai dan terbagi menjadi 2 bagian partisi :
kanan 1 kanan
2
5
|
6
|
9
|
8
|
x y
Langkah
9: pada partisi kanan 1 pivotnya adalah (4+5)/2=4,5 karena int tidak mengenal pecahan
maka dibulatkan menjadi 4 , pivot = [4] = 5 kemudian di cek (data x = pivot)
maka x tetap, di cek (data y > pivot) maka y mundur satu langkah menjadi
y-1=5 sehingga nilai x=y sorting selesai tanpa adanya perubahan
9
|
8
|
x y
Langkah
10: pada partisi kanan 2 pivotnya adalah (7+8)/2=7,5 karena int tidak mengenal
pecahan maka dibulatkan menjadi 7 , pivot = [7] = 9, kemudian di cek (data x =
pivot) maka x tetap pada indeks[7], (data y < pivot) dan syarat terpenuhi
maka data pada indeks [7] dan [8] ditukar, setelah posisi ditukar maka x
bergeser ke kanan (x+1=1) dan y bergeser ke kiri (y-1=1).
8
|
9
|
karena x > y maka sorting
selesai.
Untuk
lebih jelasnya perhatikan gambar berikut ini :
[0] [1] [2] [3] [4] [5] [6] [7] [8]
6
|
2
|
9
|
5
|
4
|
1
|
7
|
3
|
8
|
x
y
6
|
2
|
9
|
5
|
4
|
1
|
7
|
3
|
8
|
x
y
3
|
2
|
9
|
5
|
4
|
1
|
7
|
6
|
8
|
x
y
3
|
2
|
9
|
5
|
4
|
1
|
7
|
6
|
8
|
x y
3
|
2
|
1
|
5
|
4
|
9
|
7
|
6
|
8
|
x y
3
|
2
|
1
|
4
|
5
|
9
|
7
|
6
|
8
|
3
|
2
|
1
|
5
|
9
|
7
|
6
|
8
|
x y x y
1
|
2
|
3
|
5
|
9
|
7
|
6
|
8
|
1
|
3
|
5
|
6
|
7
|
9
|
8
|
1
|
3
|
5
|
6
|
9
|
8
|
x y x y
1
|
3
|
5
|
6
|
8
|
9
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Berikut
Program untuk Quick Sort :
#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<<"Data sebelum diurutkan:
"<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}cout<<"\n";
quick_sort(data,0,n-1);//hasil pengurutan
cout<<"hasil pengurutan:\n";
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}getch();
}
jika kalian ingin dokumennya silahkan download disini : ACADEMIA
Tidak ada komentar:
Posting Komentar