Quick Sort adalah salah satu algoritma pengurutan data yang paling cepat, yaitu dengan membagi list menggunakan sebuah pivot. Quick Sort juga menggunakan rekursif dalam algoritmanya. Data yang kurang dari pivot sudah ditentukan ditaruh disebelah kirinya pivot sedangkan data yang lebih besar dari pivot maka ditaruh disebelah kanan pivot.
Source Image : https://id.wikipedia.org/wiki/Berkas:Sir_Tony_Hoare_IMG_5125.jpg
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.
Kelebihan Quick sort:
- Secara umum memiliki kompleksitas O(n log n).
- Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
- Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti mergesort dan heapsort.
- Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
- Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).
Kekurangan Quick short
- Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
- Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).
- Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
- Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.
- Pada bahasa pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class TList dan TStringList dalam Delphi (Object Pascal) maupun FreePascal.
Contoh Pengurutan Quick Short
dalam hal ini saya punya angka sebagai berikut.
langkah pertama adalah tentukan pivotnya. dalam hal ini adalah saya memilih angka 7
kemudian buat partisi buat masing2 angka sebelah kanan dan kiri
kemudian gunakan algoritma quicksort yang ada diatas. jika angka lebih kecil dari pivot maka akan diletakan sebelah kiri dan jika lebih besar maka letakan disebelah kanan. langkah pertama adalah bandingkan angka 9 dengan pivot apakah lebih kecil atau lebih besar.
karena angka 9 lebih besar maka letakan angka 9 setelah pivot.
lanjut ke angka 4. bandingkan angka 4 dengan pivot.
karena angka 4 lebih kecil dari 7 maka posisi tetap.
lanjut ke angka 2. cek apakah angka 2 lebih kecil atau lebih besar dari pivot.
karena angka 2 lebih kecil dari pivot maka letaknya tetap
bandingkan pivot dengan angka 10. cek angka 10 ebih besar atau lebih kecil dari pivot.
karena angka 10 lebih besar maka posisi tetap sebelah kanan
lanjut ke angka 1. cek angka 1 lebih kecil atau lebih besar dari pivot.
karena lebih kecil maka pindah ke sebelah kiri pivot.
lanjut ke angka 5. cek apakah angka 5 lebih kecil atau lebih besar dari angka pivot.
karena angka 5 lebih kecil maka pindah ke sebelah kiri pivot.
setelah itu masuk ke dalam partisi baru. sampai sini proses belum selesai.
tentukan pivot untuk masing-masing partisi
perbandingan untuk pivot pertama. angka 2. cek apakah angka 2 lebih kecil atau lebih besar dari pivot.
karena angka 2 lebih kecil dari pivot maka pindahkan ke kiri pivot.
lanjut ke angka 1. cek apakah angka lebih besar atau lebih kecil dari pivot.
karena angka 1 lebih kecil maka pindahkan disebelah kiri angka pivot.
lanjut ke angka 5. cek apakah angkanya lebih besar atau lebih kecil dari pivot.
karena lebih besar maka posisinya tetap. untuk partisi pertama selesai
ulangi langkah2 seperti sebelumnya untuk pivot partisi ke 2. dan hasil akhir dari quick sort ini adalah seperti ini :
Daftar Referensi :
- http://onophp.blogspot.com/2018/11/quick-sort-pengertian-agoritma-dan.html
- http://catatan-ati.blogspot.com/2015/08/pengertian-quick-sort-dan-implementasi.html
- https://binus.ac.id/bandung/2019/12/algoritma-quick-sort-di-python/
