Algorisme de selecció

De Viquipèdia
Jump to navigation Jump to search

En ciències de la computació, un algorisme de selecció és un algorisme dissenyat per trobar el k-èsim nombre més petit en una llista o vector. Aquest nombre s'anomena ordre estadístic k. La selecció és un subproblema de problemes més complexos com els del veí més proper o camí més curt. Molts algorismes de selecció deriven de la generalització d'algorismes d'ordenació, i recíprocament alguns algorismes d'ordenació poden derivar-se en repetides aplicacions de selecció.

L'algorisme de selecció més senzill és el problema de trobar el mínim o màxim element d'una llista per iteració, fent un seguiment del valor mínim )o màxim) actual durant aquesta. D'altra banda, trobar la mediana és l'algorisme de selecció més complex, el qual necessita una memòria n/2 (essent n el nombre d'elements de la llista o vector).

Referències[modifica]