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.

Algoritma minimum/maksimum linear

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.

Algoritma seleksi umum nonlinear

Dengan memakai ide yang sama yang digunakan dalam algoritma minimum/maksimum, kita dapat mengkonstruksi sebuah algoritma sederhana tapi tidak efisien untuk menemukan item terkecil ke-k atau terbesar ke-k, yang membutuhkan waktu O(kn), yang efektif untuk k yang kecil. Untuk memperolehnya, kita cukup menemukan nilai paling ekstrem dan memindahnya ke bagian awal sampai kita mendapatkan indeks yang diinginkan. Hal ini dapat dilihat sebagai pengurutan seleksi yang tidak lengkap. Berikut ini adalah algoritma berbasis minimum:

 function select(a[1..n], k)
     for i from 1 to k
         minIndex = i
         minValue = a[i]
         for j = i+1 to n
             if a[j] < minValue
                 minIndex = j
                 minValue = a[j]
         swap a[i] and a[minIndex]
     return a[k]

Keuntungan lain dari metode ini adalah:

• Setelah mengetahui lokasi elemen terkecil ke-j, waktu yang dibutuhkan hanya O(j + (k-j)²) untuk menemukan elemen terkecil ke-k, atau hanya O(k) untuk k ≤ j.
• Metode ini dapat dilakukan dengan struktur data list berkait, dimana list terbut berbasis partisi yang membutuhkan pengaksesan acak.