Algoritma quicksort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di Computer Journal 5 pada April 1962. Bentuknya yang sederhana, efisien dan efektif dengan cepat membuatnya menjadi algoritma pengurutan (sorting) yang paling banyak digunakan, terutama dalam bahasa pemrograman. Berbagai penelitian dan pengembangan telah banyak dilakukan hingga saat ini.
Tercatat peneliti seperti Sedgewick, Bentley, McIlroy, Clement, Flajolet, Vallee, hingga Martinez, membuat analisis dan implementasi dari quicksort. Berikut ini merupakan kelebihan dan kekurangan dari algoritma quick sort adalah sebagai berikut :
Kelebihan dan Kekurangan Algoritma Quick Sort
- Kelebihan Algoritma 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 Algoritma 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 ).
- 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.
Pembahasan lainnya :
Originally posted 2022-10-12 00:21:17.
