Quicksort merupakan Algoritma Sorting yang dikembangkan oleh C.A.R Hoare pada tahun1960 yang secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting pergantian pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n 2 ), walaupun kejadian seperti ini sangat langka. Quick sort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).
Pada masalah pengurutan data bilangan bulat (integer) secara terindeks pada suatu list atau array dari bilangan yang paling besar sampai ke bilangan yang paling kecil atau sebaliknya. Tidak hanya dapat diterapkan pada pengindeksan bilangan saja, namun juga untuk pengindeksan huruf (abjad) dari A ke Z atau sebaliknya. Algoritma ini sangat baik diterapkan pada kasus pengindeksan kumpulan kata (library sort utility) atau kumpulan bilangan atau kombinasinya.
Langkah-Langkah Algoritma Quick Sort
-
-
Divide
Memilah rangkaian data menjadi dua subrangkaian A[p…q-1] dan A[q+1…r] dimana setiap unsur A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap unsur pada A[q+1…r] adalah lebih besar atau sama dengan unsur pada A[q]. A[q] disebut sebagai unsur pivot. Perhitungan pada unsur q merupakan salah satu bagian dari prosedur pemisahan.
-
Conquer
Mengurutkan unsur pada subrangkaian secara rekursif Pada algoritma quicksort, langkah ”kombinasi” tidak dilakukan karena telah terjadi pengurutan unsur – unsur pada sub-array. Quicksort termasuk pada pendekatan sulit membagi, mudah menggabung (hard split/easy join).
-
Cara pemilihan pivot :
- Pivot = unsur pertama/unsur terakhir/unsur tengah tabel
- Pivot dipilih secara acak dari salah satu unsur tabel
Pivot = unsur median tabel
Algoritma ini terdiri dari 4 langkah utama :
-
- Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data tersebut itu apa adanya.
- Ambil sebuah elemen yang akan digunakan sebagai pivot point (point poros). (biasanya elemen yang paling kiri).
- Bagi struktur data menjadi dua bagian, satu dengan elemen-elemen yang lebih besar dari pada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
- Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.
Pembahasan lainnya :
