Quick Sort Algoritma Raptor dan Java
QUICK SORT
Algoritma quick sort diperkenalkan pertama kali oleh C.A.R. Hoare
pada tahun 1960, dan dimuat sebagai artikel di “Computer Journal 5” pada April
1962. Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan
metoda divide-and-conqueror. 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 sort dilakukan per
partisi
Teknik mempartisi tabel:
I.
pilih x ϵ {a1, a2, …, an} sebagai elemen pivot.
II.
pindai (scan) tabel dari kiri sampai ditemukan elemen
ap ≥ x.
III. pindai
tabel dari kanan sampai ditemukan elemen aq ≤ x
IV. pertukarkan
ap <-> aq
V.
ulangi (ii) dari posisi p + 1, dan (iii) dari posisi q
– 1, sampai kedua pemindaian bertemu di tengah tabel.
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.
Walaupun begitu algoritma quick sort
tidak selalu merupakan pilihan yang terbaik. Seperti yang telah disebutkan
sebelumnya, algoritma ini dilakukan secara rekursif yang berarti jika dilakukan
untuk tabel yang berukuran sangat besar, walaupun cepat, dapat menghabiskan
memori yang besar pula. Selain itu, algoritma ini adalah algoritma yang terlalu
komplex untuk mengurutkan tabel yang berukuran kecil (hanya puluhan elemen
misalnya). Selain itu algoritma quick sort mempunyai tingkat efisiensi yang buruk
ketika dioperasikan pada tabel yang hampir terurut atau pada tabel yang terurut
menurun.
Ø
Algoritma Quick Sort
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 tabel. Cara ini hanya bagus jika elemen tabel tersusun secara
acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika
elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel
kanan.
2.
Pivot dipilih secara acak dari salah satu elemen tabel.
Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan
prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.
3.
Pivot adalah elemen median tabel. Cara ini paling
bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran
seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu
yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut
adalah persoalan tersendiri.
ALGORITMA
s
1.
ILUSTRASI QUICK SORT
Lokasi
|
1
|
2
|
3
|
4
|
5
|
6
|
Data
|
25
|
27
|
10
|
8
|
76
|
21
|
Patokan
= 25
Lokasi
|
1
|
2
|
3
|
4
|
5
|
6
|
Kn
|
*
|
27
|
10
|
8
|
76
|
21
|
Kr
|
21
|
27
|
10
|
8
|
76
|
*
|
Kn
|
21
|
*
|
10
|
8
|
76
|
27
|
Kr
|
21
|
8
|
10
|
*
|
76
|
27
|
21
|
8
|
10
|
25
|
76
|
27
|
Patokan
= 21
Lokasi
|
1
|
2
|
3
|
4
|
5
|
6
|
*
|
8
|
10
|
25
|
76
|
27
|
|
Kn
|
10
|
8
|
*
|
|||
Kr
|
10
|
8
|
21
|
Patokan
= 10
Lokasi
|
1
|
2
|
3
|
4
|
5
|
6
|
*
|
8
|
21
|
25
|
76
|
27
|
|
Kn
|
8
|
10
|
Patokan
= 76
Lokasi
|
1
|
2
|
3
|
4
|
5
|
6
|
8
|
10
|
21
|
25
|
*
|
27
|
|
Kn
|
27
|
76
|
Hasil
Lokasi
|
1
|
2
|
3
|
4
|
5
|
6
|
Hasil
|
8
|
10
|
21
|
25
|
27
|
76
|
RAPTOR
Tab Main |
Tab Data |
Tab Tampilan |
Tab Quick Sort |
Lanjuta Tab Quick Sort |
SELAMAT MENCOBAN
SALAM SEJATRA
Komentar
Posting Komentar