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).^[1]

L'algorisme de selecció conegut amb millor eficiència és el Quickselect, que està relacionat amb l'algorisme d'ordenament Quicksort.

Selecció per ordenament

Ordenant la llista o la matriu i seleccionant l'element desitjat, la selecció es pot reduir a un problema d'ordenació.^[2] Aquest mètode és ineficient per seleccionar un únic element, però és eficient si un cop ordenat s'utilitza per seleccionar diversos elements. El cost computacional de l'ordenament es pot reduir utilitzant algorismes d'ordenació no comparatius com l'ordenament Radix o l'ordenament per comptatge. A més, en lloc d'ordenar tota la llista o matriu, es pot utilitzar ordenament parcial per seleccionar els k elements més petits o més grans.

Referències

↑ 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.
↑ 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.

[1] 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.

[2] 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.

[1]

[2]