Quicksort adalah algoritma pengurutan yang efisien, dikembangkan oleh ilmuwan komputer Inggris Tony Hoare pada tahun 1959 dan diterbitkan pada tahun 1961. Ini adalah algoritma berbasis perbandingan, yang berarti mengukur perbedaan antara elemen yang akan diurutkan. Ini beroperasi dengan memanfaatkan pendekatan membagi dan menaklukkan, yang membagi elemen menjadi dua subkelompok, yang kemudian diurutkan secara rekursif.
Quicksort menggunakan kombinasi pengurutan pilihan dan partisi untuk mengurutkan array. Dalam pengurutan pilihan, algoritma mencari elemen terkecil dalam array dan menukarnya dengan elemen pertama dalam array. Pertukaran ini memastikan bahwa elemen terkecil selalu berada di awal array. Tahap partisi kemudian memindahkan nilai elemen saat ini ke tempat antara elemen dengan nilai yang lebih kecil dan lebih besar darinya. Hal ini dilakukan dengan terlebih dahulu memilih elemen array, yang dikenal sebagai “pivot”. Semua elemen yang lebih kecil dari poros ditempatkan sebelum poros, dan semua elemen yang lebih besar dari poros ditempatkan setelahnya. Proses ini diulangi dengan dua subgrup yang baru dibuat hingga array diurutkan.
Kompleksitas waktu quicksort bergantung pada pivot yang dipilih, namun pada sebagian besar kasus, kompleksitas waktu quicksort adalah O(n log n). Hal ini menjadikan quicksort sebagai algoritma pengurutan pilihan, karena kecepatannya yang relatif cepat. Ini juga lebih disukai karena kebutuhan memorinya yang rendah.
Quicksort banyak digunakan di banyak bidang ilmu komputer, seperti sistem operasi, database, dan grafik. Ini juga sering digunakan sebagai bagian dari perpustakaan standar dalam banyak bahasa pemrograman seperti C, Java, dan Python.
