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
                                                                          NETBEANS/ JAVA

                SELAMAT MENCOBAN 
                SALAM SEJATRA





Komentar

Postingan Populer