|
Dalam [[ilmu komputer]], sebuah '''algoritmaalgoritme pemilihan''' adalah sebuah [[algoritmaalgoritme]] 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. AlgoritmaAlgoritme ini disebu juga ''orde statistik''. Terdapat algoritmaalgoritme yang relatif sederhana untuk menemukan, minimum, maksimum, dan element terkecil ke-''k'' dengan waktu linear. AlgoritmaAlgoritme 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 algoritmaalgoritme pengurutan ==
Satu algoritmaalgoritme seleksi yang sederhana dan digunakan secara luas adalah memanfaatkan [[algoritmaalgoritme pengurutan]] pada list, kemudian mengekstrak elemen ke-''k''. Ini adalah contoh [[reduksi (kompleksitas)|reduksi]] satu permasalahan ke dalam permasalahan lain. Hal ini bermanfaat ketika kita ingin melakukan banyak seleksi terhadap sebuah list tunggal, dimanadi mana kasus ini membutuhkan hanya satu operasi pengurutan di awal yang membutuhkan waktu yang lama (''expensive''), yang diikuti oleh banyak operasi ekstraksi yang sebentar (''[http://www.top-cheap.com Cheap] {{Webarchive|url=https://web.archive.org/web/20200923084727/https://www.top-cheap.com/ |date=2020-09-23 }}''). 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, dimanadi mana ''n'' adalah panjang dari list.
==Algoritma Algoritme minimum/maksimum linear ==
Kasus terburuk algoritmaalgoritme 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''), algoritmaalgoritme 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 Algoritme seleksi umum nonlinear ==
Dengan memakai ide yang sama yang digunakan dalam algoritmaalgoritme minimum/maksimum, kita dapat mengkonstruksi sebuah algoritmaalgoritme 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 ekstrimekstrem dan memindahnya ke bagian awal sampai kita mendapatkan indeks yang diinginkan. Hal ini dapat dilihat sebagai [[pengurutan seleksi]] yang tidak lengkap. Berikut ini adalah algoritmaalgoritme berbasis minimum:
'''function''' select(a[1..n], k)
Keuntungan lain dari metode ini adalah:
* Setelah mengetahui lokasi elemen terkecil ke-''j'', waktu yang dibutuhkan hanya O(''j'' + (''k''-''j'')<sup>2</sup>) untuk menemukan elemen terkecil ke-''k'', atau hanya O(''k'') untuk ''k'' ≤≤ ''j''.
* Metode ini dapat dilakukan dengan struktur data [[list berkait]], dimanadi mana list terbut berbasis partisi yang membutuhkan [[pengaksesan acak]].
{{rintisanalgoritme-stub}}
[[Kategori:AlgoritmaAlgoritme]]
[[Kategori:AlgoritmaAlgoritme Pencarian]]
[[en:Selection algorithm]]
| 