Algoritme 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.
Algoritme seleksi
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, 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.