Algoritma Quickselect

Intro

Tahun lalu waktu lagi persiapan interview, tiba-tiba kepikiran, bagaimana kalau nanti pas lagi interview ditanya tentang algoritma Quickselect dan bagaimana cara membuktikan bahwa algoritma Quickselect dapat bekerja dalam kompleksitas $O(N)$. Teringat kembali waktu masih belajar tentang rekursi di kelas Desain Analisis & Algoritma (DAA) waktu kuliah dan mencoba membuka kembali ingatan waktu itu. Butuh waktu yang cukup lama untuk mempelajari algoritma ini kembali, padahal dulu waktu belajar teringat cukup mudah.

Terus setelah memahami kembali dan takut akan lupa lagi, jadinya aku nulis post kecil-kecilan kayak gini tentang apa aja yang udah kupelajari dengan harapan semoga kalau nanti di masa depan aku lupa lagi sama topik ini, aku bisa menggunakan post ini buat dibaca. Ini juga sesuai dengan teknik Feynman dalam belajar yaitu belajar dengan mengajar. Semoga post ini dapat berguna juga bagi pembaca post ini.

Latar Belakang Permasalahan

Sebelum masuk terlalu dalam ke definisi algoritma Quickselect, di sini aku mau mencoba menjelaskan terlebih dahulu permasalahan apa yang ingin diselesaikan dengan algoritma Quickselect.

Misalkan kita diberikan $N$ buah bilangan bulat positif. Kita ingin mencari elemen terkecil ke-$K$. Bagaimana cara paling efisien untuk menyelesaikannya?

Salah satu solusi yang cukup mudah dan intuitif adalah dengan melakukan sorting terlebih dahulu menggunakan algoritma sorting yang cepat seperti Mergesort atau Quicksort. Kemudian kita cukup mengakses elemen ke-$K$ pada barisan bilangan yang telah diurutkan tersebut. Algoritma ini akan memiliki kompleksitas waktu $O(N \log N)$.

Cara lain yang dapat digunakan adalah dengan menggunakan sedikit modifikasi pada algoritma Selection Sort dimana kita mencari elemen terkecil pertama, kedua, ..., hingga ke-$K$. Tetapi algoritma ini sendiri juga memiliki kompleksitas waktu $O(NK)$ dimana untuk nilai $K$ yang besar akan membuat algoritma ini memiliki worst case berupa $O(N^2)$.

Apakah ada algoritma yang lebih cepat selain kedua algoritma di atas untuk menyelesaikan permasalahan tersebut? Tentu saja ada! Quickselect!

Apa itu Quickselect

Apabila kalian pernah mempelajari algoritma Quicksort sebelumnya, maka algoritma Quickselect ini akan terdengar familiar. Karena pada awalnya algoritma Quickselect ini dibahas pertama kali pada paper pertama yang membahas Quicksort. Ide utama dari algoritma ini adalah menggunakan Decrease and Conquer variasi dari Divide and Conquer dimana kita membagi permasalahan menjadi subproblem yang lebih kecil sehingga jumlah operasi yang diperlukan juga menjadi lebih sedikit.

Berikut kurang lebih isi dari algoritma Quickselect ini

Oke-oke, jika kalian bingung saat membaca algoritma di atas, atau bahkan takut dengan panjangnya teks di atas dan langsung skip ke bagian ini, tidak apa-apa. Karena di bagian ini aku akan coba menjelaskan algoritma Quickselect ini secara bertahap.

Analasis kompleksitas

Bagaimana dengan kompleksitas algoritma ini? Kalau kita lihat secara sekilas jumlah operasi yang kita lakukan akan sebanyak jumlah elemen pada array yaitu $|array|$ ditambah dengan jumlah elemen pada array setelah dipecah menjadi subproblem. Secara simpel, banyak iterasi yang dilakukan dapat ditulis sebagai berikut $quickselect(arr) = len(arr) + quickselect(newarr)$. Dimana newarr adalah array baru yang tercipta setelah langkah ketiga.

Untuk perhitungan kasus terbaik dan kasus terburuk pada algoritma ini, kita misalkan pada awalnya terdapat $N$ buah elemen. Setelah memilih sebuah pivot secara acak, maka kita akan membagi array menjadi 2 bagian dengan panjang antara $N - k$ dan $k$ dimana $k$ adalah sebuah nilai konstanta yang bergantung pada performa pivot yang kita pilih. Sehingga fungsi tersebut akan menjadi $quickselect(arr) = len(arr) + quickselect(arr_{k})$ atau $quickselect(arr) = len(arr) + quickselect(arr_{N-k})$. Dimana $arr_k$ adalah array yang terdiri dari $k$ elemen dan $arr_{N-k}$ adalah array yang terdiri dari $N-k$ elemen.

Di sini kita dengan asumsi kasus terburuk, kita akan selalu milih array dengan jumlah elemen yang lebih banyak sehingga fungsi akan menjadi $quickselect(arr) = len(arr) + quickselect(arr_{max(N-k, k)})$.

Kasus terbaik akan terjadi pada saat nilai dari $N-k = k$. Dimana nilai dari $k$ akan sama dengan $N/2$. Sehingga pada setiap pemecahan subproblem kita mengubah array dengan panjang $N$ menjadi $\frac{N}{2}$. Sehingga fungsi kita akan menjadi $quickselect(arr) = len(arr) + quickselect(array_{len(arr)/2})$. Sehingga apabila dijabarkan, akan didapatkan total perhitungan operasi sebagai berikut $N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + ... + 1 = 2N$ menggunakan jumlah deret geometri $S = \frac{a}{(1 - r)}$, dimana $a = N$ dan $r = 1/2$ didapatkan $\frac{N}{1-\frac{1}{2}} = \frac{N}{1/2} = 2N = O(N)$.

Sedangkan kasus terburuk akan terjadi apabila pemilihan pivot tidak optimal dimana kita memilih pivot sehingga nilai dari salah satu $N - k$ atau $k$ menjadi sangat besar yaitu $max(N-k, k) = N - 1$. Sehingga fungsi kita akan menjadi $quickselect(arr) = len(arr) + quickselect(array_{len(arr - 1)})$. Sehingga apabila dijabarkan, akan didapatkan total perhitungan operasi sebagai berikut $N + (N - 1) + (N - 2) + (N - 3) + ... + 1 = O(N^2)$.

Dapat dilihat di atas kompleksitas algoritma Quickselect ini memiliki kompleksitas $O(N)$ dan kasus terburuk $O(N^2)$, bagaimana dengan kasus rata-rata? Apakah aman untuk menggunakan algoritma ini secara umum? Ya, apabila kita memilih pivot secara acak maka kompleksitas rata-rata adalah $O(N)$. Bagaimana pembuktiannya?

def quickselect(array, k) {
    pivot = random(array) # pilih pivot secara acak
    left = []
    right = []
    for elem in array {
        if elem < pivot {
            left.push(elem)
        } else if elem > pivot {
            right.push(elem)
        }
    }
    if len(left) > k {
        # kalau jumlah element < pivot lebih banyak dari k
        # cari pada array dengan elemen lebih kecil dari pivot
        return quickselect(left, k)
    } else if len(left) + 1 < k {
        # sebaliknya, cari pada array dengan elemen lebih besar
        return quickselect(right, k - len(left) - 1)
    } else {
        # elemen terkecil ke-k adalah pivot
        return pivot
    }
}

Pembuktian kompleksitas rata-rata

Misalkan pivot yang kita pilih merupakan 50% elemen tertengah* saat diurutkan.

Maka kita pasti mendapatkan pembagian pada operasi pemecahan subproblem terburuk menjadi 25% dan 75%. Yaitu saat pivot yang kita pilih berada di antara elemen ke 25% atau 75% (daerah yang diarsir). Dapat kita lihat bahwa kasus terburuk adalah kita akan mengubah array dengan panjang $N$ menjadi $75\%$-nya atau sebanyak $\frac{3}{4}N$. Sehingga total perhitungan operasi akan menjadi $N + \frac{3}{4}N + \frac{9}{16}N + \frac{27}{64}N + ... + 1$. Tetapi ini belum semuanya, karena ini masih menggunakan asumsi bahwa pivot yang kita pilih akan selalu berada di 50% elemen tertengah dimana pada kenyataan hal tersebut belum terbukti. Kita tau bahwa probabilitas untuk mendapatkan 50% elemen tertengah apabila kita memilih pivot secara acak adalah $\frac{1}{2}$. Maka expected value pivot yang kita pilih merupakan 50% elemen tertengah adalah 2 (secara intuitif apabila kita tahu probabilitas elemen adalah 1/2, maka kira-kira dibutuhkan dua kali percobaan). Maka banyak operasi akan menjadi $2N + \frac{3}{4}2N + \frac{9}{16}2N + \frac{27}{64}2N + ... + 1$ yang ekuivalen dengan $2(N + \frac{3}{4}N + \frac{9}{16}N + \frac{27}{64}N + ... + 1)$. Menggunakan jumlah deret geometri dimana nilai $a = N$ dan $r = \frac{3}{4}$ didapatkan $2\frac{N}{1 - \frac{3}{4}} = 2 \frac{N}{\frac{1}{4}} = 2 × 4N = 8N = O(N)$. Terbukti bahwa kompleksitas rata-rata dari algoritma ini adalah $O(N)$.

Penutup

Dulu sebelum aku mengenal algoritma Quickselect, aku tidak pernah tau kalau ada cara yang lebih cepat untuk menyelesaikan permasalahan mencari elemen terkecil ke-$K$ selain menggunakan algoritma sorting. Saat pertama kali mendengar algoritma ini, aku lumayan terpukau dengan cara kerja algoritma ini karena walau terlihat cukup sederhana, algoritma ini memiliki kompleksitas yang efisien.

Terdapat juga algoritma lain yang dapat digunakan untuk mencari elemen terkecil ke-$k$ yaitu dengan menggunakan Median of Medians yang memiliki kompleksitas waktu $O(N)$ pada kasus terburuk. Tetapi algoritma ini memiliki konstanta yang lebih besar dibandingkan dengan algoritma Quickselect dan sedikit lebih rumit untuk diimplementasikan.

Terima kasih sudah membaca post ini sampai akhir, semoga bisa bermanfaat! :D