Algoritma - Quicksort, apa itu?
Di post kali ini, saya akan bahas salah satu hal yang menarik yang telah saya pelajari yaitu algoritma quicksort.
Apa Itu quicksort?
Quicksort merupakan algoritma pengurutan (sorting) data yang memiliki pendekatan rekursif, quicksort performanya lebih cepat jika dibandingkan dengan algoritma selection sort.
Quicksort digunakan untuk mengurutkan sebuah array, namun ada beberapa array yang tidak perlu dilakukan pengurutan seperti array kosong dan array dengan satu element.
Array dengan dua element akan mudah untuk diurutkan, contoh:
Bagaimana dengan array dengan tiga element?
Ingat, quicksort menggunakan teknik divide & conquer (DC) maka array tersebut haruslah di-break down sampai menemukan base case-nya.
Pertama, ambil satu element dari array yang disebut dengan pivot yang bisa berupa element pertama atau element terakhir.
Kemudian temukan element yang lebih kecil dan lebih besar dari pivot.
Sekarang kita memiliki sebuah pivot, sub-array yang lebih kecil dari pivot dan sub-array yang lebih besar dari pivot, yang disebut dengan partitioning.
Karena kedua sub-array diatas sudah terurut, jadi kita sudah mendapatkan sebuah array yang terurut (sorted).
Bagaimana jika mengambil pivot yang berbeda? katakanlah kita mengambil pivot dari element terakhir yaitu 8.
Maka kita akan memiliki partitioning seperti berikut ini:
Sub-array yang lebih besar dari pivot berisi array kosong (empty array), sub-array yang lebih kecil dari pivot belum terurut (sorted) maka kita perlu mengurutkan sub-array tersebut, which is kita sudah mengetahui cara mengurutkan 2 element array (base case quicksort)
Maka akan didapatkan hasil: [2,4] + [8] + [] = [2,4,8]
Jadi cara mengurutkan sebuah array dengan quicksort adalah sebagai berikut:
1. Mengambil pivot
2. Partitioning array tersebut menjadi dua sub-array: element yang lebih kecil dari pivot dan element yang lebih besar dari pivot
3. Memanggil quicksort secara rekursif pada kedua sub-array.
Dengan menggunakan logika yang sama, kita bisa melakukan sorting berapapun element yang dimiliki oleh sebuah array.
Implementasi quicksort dengan JavaScript
Reference book: Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People.
