Algoritma seleksi

Dalam ilmu komputer, sebuah algoritme pemilihan adalah sebuah algoritme 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. Algoritme ini disebu juga orde statistik. Terdapat algoritme yang relatif sederhana untuk menemukan, minimum, maksimum, dan element terkecil ke-k dengan waktu linear. Algoritme 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 algoritme pengurutan

Satu algoritme seleksi yang sederhana dan digunakan secara luas adalah memanfaatkan algoritme 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, di mana kasus ini membutuhkan hanya satu operasi pengurutan di awal yang membutuhkan waktu yang lama (expensive), yang diikuti oleh banyak operasi ekstraksi yang sebentar (Cheap Diarsipkan 2020-09-23 di Wayback Machine.). 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, di mana n adalah panjang dari list.

Algoritme minimum/maksimum linear

Kasus terburuk algoritme 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), algoritme 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.

Algoritme seleksi umum nonlinear

Dengan memakai ide yang sama yang digunakan dalam algoritme minimum/maksimum, kita dapat mengkonstruksi sebuah algoritme 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 algoritme 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, di mana list terbut berbasis partisi yang membutuhkan pengaksesan acak.