Algorisme de selecció
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ènciesModifica
| Caldria contextualitzar les obres citades al cos de l'article. |
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.