Quick Sort- Quick Sort adalah algoritma pengurutan yang paling cepat dan paling banyak digunakan dalam pengurutan data. Quick Sort sering disebut juga dengan Partition Exchange Sort, karena dalam proses pengurutannya membagi-bagi data menjadi beberapa partisi-partisi dan dibandingkan dalam partisi-partisi tersebut.
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 merge sort.
- Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).
Kelemahan Quick Sort
- 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).
- Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.
Algoritma Quick Sort
Pertama sekali
quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil:
element kecil dan element besar. Quicksort kemudian dapat menyortir sub list
itu secara rekursif.
Langkah-Langkah pengerjaannya ialah:
1.
Ambil sebuah elemen,
yang disebut dengan pivot, pada sebuah daftar.
2.
Urutkan kembali sebuah
list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot,
sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada
setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah
pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition.
3.
Sub list kemudian
disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen
yang lebih besar.
Kasus dasar dari rekusrif ialah list dari besaran nol atau satu,
yang tidak perlu untuk di sorting.
0 comments:
Post a Comment