Algoritma seleksi

Dalam ilmu komputer, sebuah algoritma pemilihan adalah sebuah algoritma untuk menemukan bilangan terkecil ke-k (bilangan terbesar ke-k) dalam sebuah list. Termasuk di dalamnya adalah kasus sederhana yang lazim yaitu menemukan elemen minimum, maksimum dan median. Algoritma ini disebu juga orde statistik. Terdapat algoritma yang relatif sederhana untuk menemukan, minimum, maksimum, dan element terkecil ke-k dengan waktu linear. Algoritma ini juga memungkinkan untuk menemukan elemen terkecil ke-k dalam waktu linear yang paling buruk atau orde statistik berlipat. Seleksi adalah sebuah sub masalah dari permasalahan yang lebih kompleks seperti permasalahan tetangga terdekat.

Seleksi dengan algoritma pengurutan

Satu algoritma seleksi yang sederhana dan digunakan secara luas adalah memanfaatkan algoritma pengurutan pada list, kemudian mengekstrak elemen ke-k. Ini adalah contoh reduksi satu permasalahan ke dalam permasalahan lain. Hal ini bermanfaat ketika kita ingin melakukan banyak seleksi terhadap sebuah list tunggal, dimana kasus ini membutuhkan hanya satu operasi pengurutan di awal yang membutuhkan waktu yang lama (expensive), yang diikuti oleh banyak operasi ekstraksi yang sebentar (cheap). Ketika kita hanya ingin melakukan satu seleksi, atau ketika kita ingin selalu mengubah list di antara tiap seleksi, metode ini dapat jadi lebih lama (costly), biasanya membutuhkan paling sedikit O(n log n) waktu, dimana n adalah panjang dari list.

Linear minimum/maximum algorithms

Kasus terburuk algoritma linear untuk menemukan minimum atau maksimum adalah sangat jelas; kita menyimpan dua peubah, satu mengacu ke indeks dari elemen minimum/maksimum yang didapatkan sementara, dan satu lagi menyimpan nilainya. Bersamaan dengan kita memindai list tersebut, kita perbarui kedua peubah tersebut jika kita menemukan sebuah elemen yang sesuai:

 function minimum(a[1..n])
     minIndex := 1
     minValue := a[1]
     for i from 2 to n
         if a[i] < minValue
             minIndex := i
             minValue := a[i]
     return minValue

 function maximum(a[1..n])
     maxIndex := 1
     maxValue := a[1]
     for i from 2 to n
         if a[i] > maxValue
             maxIndex := i
             maxValue := a[i]
     return maxValue

Sebagai catatan, kemungkinan akan terdapat banyak elemen minimum atau maksimum. Oleh karena pembandingan di atas adalah kaku (strict), algoritma tersebut menemukan elemen minimum dengan indeks yang minimum. Dengan memanfaatkan pembandingan tak kaku (non-strict) (≤ and ≥), kita akan menemukan elemen minimum dengan indeks maksimum.

Jika kita ingin menemukan kedua elemen minimum dan maksimuam bersamaan, perbaikan kecil dapat dilakukan dengan sepasang pembandingan, yaitu membandingkan elemen ganjil dan genap pada setiap pasang dan membandingkannya dengan elemen maksimum dan minimum.