Algoritmo de Selección

En ciencias de la computación, un algoritmo de selección es un algoritmo para encontrar el k-ésimo menor número en una lista o vector; a este número se le llama estadístico de orden k. Este incluye los casos de encontrar el mínimo, máximo, y la mediana. Existen algoritmos de selección O(n) (lineal en el peor caso), y algoritmos sublineales son posibles para datos estructurados; en el caso extremos, O(1) para un vector de elementos ordenados. La selección es un subproblema de otros problemas más complejos, como el y problema del camino más corto. Muchos algoritmos de selección son derivados por generalización de algún algoritmo de ordenación, y recíprocamente algunos algoritmos de ordenación pueden derivarse de repetidas aplicaciones de selección. El caso más simple de un algoritmo de selección es encontrar el mínimo (o máximo) elemento por iteración a través de la lista, manteniendo un registro del mínimo (o máximo) en cada paso de la iteración, y puede verse relacionado al selection sort. Por el contrario, el caso más complejo de un algoritmo de selección es encontrar la mediana, y este necesariamente necesita n/2 memoria. De hecho, un algoritmo de selección especializado para la mediana puede ser usado para realizar un algoritmo de selección general, como en . El algoritmo de selección más conocido es , el cual está relacionado al quicksort; como el quicksort, tiene (asintóticamente) rendimiento óptimo en la media de los casos, pero mal rendimiento en el peor caso, no obstante puede ser modificado para dar rendimiento óptimo en el peor caso también.