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 problema de la búsqueda del vecino más cercano 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 median of medians. El algoritmo de selección más conocido es quickselect, 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.

Selección por ordenamiento

Ordenando la lista o vector y luego seleccionando el elemento deseado, la selección puede ser reducido a la ordenación. Este método es ineficiente para seleccionar un único elemento, pero es eficiente cuando se realizan múltiples selecciones del vector, en este caso solo es necesario una ordenación costosa inicial, seguida por muchas operaciones poco costosas de selección – O(1) para un vector, aunque la selección es O(n) en una lista, incluso si está ordenada, debido a la falta de acceso aleatorio. En general, ordenar requiere O(n log n) tiempo, donde n es la longitud de la lista, aunque se conoce que un lower bound es posible con algoritmos de ordenación no comparativos como radix sort y counting sort.

En lugar de ordenar la lista completa o el vector, se puede usar ordenación parcial para seleccionar los k menores o k mayores elementos. Esto es más eficiente que ordenando totalmente, pero menos eficiente que seleccionando simplemente, y toma O(n + k log k) tiempo, debido al ordenamiento de los k elementos. Algoritmos de ordenamiento parcial pueden ser a menudo derivados de algoritmos de ordenación total. Así como el ordenamiento total, el ordenamiento parcial significa que posteriores selecciones (debajo del k-ésimo elemento) pueden ser hechas en tiempo O(1) en una vector y en tiempo O(k) en una lista. Además, si la ordenación parcial también particiona los datos originales en "ordenados" y "desordenados", como con un ordenado in-place, el ordenamiento parcial puede ser extendido a un ordenamiento parcial mayor por medio del ordenamiento de porciones incrementales, y si esto está hecho, posteriores selecciones sobre el k-ésimo elemento pueden ser realizadas con relativamente poco costo.

Ordenamiento por selección parcial

Un simple ejemplo de selección por ordenación parcial es usar el selection sort.

El obvio algoritmo lineal para encontrar el mínimo (resp. máximo) – iterando sobre la lista y manteniendo el actual mínimo (resp. máximo) – puede ser visto como ordenación por selección parcial que selecciona el menor elemento. Sin embargo, otras ordenamientos parciales también se reducen a esto para el caso k = 1, como el heap sort parcial.

De forma más general, un ordenamiento por selección parcial produce un simple algoritmo de selección que demora O(kn) tiempo. Esto es asintóticamente ineficiente, pero puede ser suficientemente eficiente si k es pequeño, y es fácil de implementar. Concretamente, simplemente encontramos el mínimo y lo movemos al principio, repitiendo sobre la lista restante hasta haber acumulado k elementos, y luego retornando el k-ésimo elemento. Aquí vemos un algoritmo de selección parcial por ordenamiento:

 function select(list[1..n], k)
     for i from 1 to k
         minIndex = i
         minValue = list[i]
         for j from i+1 to n
             if list[j] < minValue
                 minIndex = j
                 minValue = list[j]
                 swap list[i] and list[minIndex]
     return list[k]

Selección basada en particionamiento

Rendimiento lineal puede ser logrado por algoritmos de selección por particionamiento, el más básico quickselect. Quickselect es una variante del quicksort – en ambos uno selecciona un pivote y luego particiona los datos por él, pero mientras que el Quicksort se ejecuta a ambos lados de la partición, Quickselect solo se ejecuta en un lado, que es en el cual el k-ésimo elemento se encuentra. Así como con Quicksort, este tiene un rendimiento óptimo en el caso medio, pero pobre rendimiento en el caso peor, en este caso cuadrático.

Selección de mediana como estrategia de pivoteo

Un algoritmo de selección de mediana puede ser usado para un algoritmo de selección general o un algoritmo de ordenación, aplicándolo como estrategia de pivoteo en Quickselect o Quicksort; si el algoritmo de selección de mediana es asintóticamente óptimo (tiempo lineal), la selección resultante u ordenación también lo será. De hecho, la mediana exacta no es necesaria – una mediana aproximada es suficiente. En el algoritmo de selección de median of medians, la estrategia de pivoteo calcula una mediana aproximada y la utiliza como pivote. En la práctica el costo del cálculo del pivote es significativo, por lo que estos algoritmos no se utilizan generalmente, pero esta técnica es de interés teórico en relacionar los algoritmos de selección y ordenamiento.

Lower bounds

En The Art of Computer Programming, Donald E. Knuth discute varios lower bounds para la cantidad de comparaciones necesarias para localizar los t menores elementos de una lista no ordenada de n valores (usando solo comparaciones). Existe un lower bound trivial de n − 1 para el mínimo o el máximo de un array. Para ver porqué, considere un torneo donde cada juego represente una comparación. Dado que cada jugador excepto el ganador del torneo debe perder un juego antes de conocer al ganador, tenemos un lower bound de n − 1 comparaciones.

La historia se hace más compleja para otros índices. Definamos $W_{t}(n)$ como el mínimo número de comparaciones necesarias para encontrar los t menores elementos. Knuth referencia el artículo publicado por S. S. Kislitsyn, que muestra un upper bound de este valor:

$W_{t}(n)\leq n-t+\sum _{n+1-t<j\leq n}\lceil {\log _{2}\,j}\rceil \quad {\text{for}}\,n\geq t$

Este límite es alcanzable para t=2 pero mejores, y más complejos límites son conocidos para mayores t.

Complejidad espacial

La complejidad espacial de la selección es k + O(1) (o n − k si k > n/2), y los algoritmos pueden seleccionar con solo O(1) memoria adicional. k memoria es necesario como los siguientes datos ilustran: comencemos con 1, 2, ..., k, y luego continuemos con k + 1, k + 1, ..., k + 1, y finalmente terminemos con j copias del 0, donde j va desde 0 hasta k − 1. En este caso el k menor elemento es uno de 1, 2, ..., k, dependiendo de la cantidad de ceros (0), pero esto solo puede ser determinado al concluir. Uno debe almacenar los k elementos iniciales hasta el terminar, dado que uno no puede reducir la cantidad de posibilidades por debajo de estos k menores valores hasta que existan menos de k elementos por ver. Notar que la selección del mínimo (o máximo) es un caso especial de esto, con k = 1.

Esta complejidad en memoria puede ser alcanzada haciendo ordenamientos parciales progresivos - manteniendo una lista ordenada de los k elementos hasta el momento, así como la ordenación por inserción parcial vista anteriormente. Notar, sin embargo, que la selección por ordenación parcial, mientras es eficiente en memoria, tiene complejidad superlineal, y que los algoritmos de selección basados en partición y eficientes en tiempo requieren O(n) memoria.

El límite de la complejidad en memoria explica la cercana conexión enter seleccionar el k-ésimo elemento y seleccionar los k menores elementos (no ordenados), como se puede ver que seleccionar el k-ésimo elemento eficientemente requiere seleccionar los k menores elementos como paso intermedio.

Algoritmo de selección en línea

La selección en línea puede ser vista como el cálculo del k-ésimo menor elemento de un flujo de datos, en el cual los algoritmos de ordenamiento parcial (con k + O(1) memoria para los k menores elementos hasta el momento) pueden ser usados, pero los basados en partición no.

Alternativamente, la selección en si puede ser requerida en línea, esto es, un elemento solo puede ser seleccionado de una entrada secuencial mediante observación y selección local, o rechazo, los cuales son irrevocables. El problema de selección, con estas restricciones, produce la respuesta óptima bajo condiciones de independencia; además es óptimo en sí mismo como algoritmo con la cantidad de cálculo lineal con respecto al tamaño de la entrada.

El ejemplo más simple es el problema de la secretaria de seleccionar el máximo con la alta probabilidad, en el que la estrategia óptima (en datos aleatorios) es mantener el rastro del máximo actual de los primeros n/e y rechazar los otros, y luego seleccionar el primer elemento que es mayor que este máximo.

Problemas relacionados

Uno podría generalizar el problema de selección a ser aplicado a rangos dentro de una lista, dando lugar al problema de consultas en rango. La pregunta de mediana de consultas en rango (calcular las medianas de múltiples rangos) ha sido analizada.

Soporte en lenguajes de programación

Muy pocos lenguajes tienen soporte integrado para selección general, sin embargo muchos proveen facilidades para encontrar el menor o el mayor elemento de una lista. Una notable excepción es C++, el cual provee un método nth_element el cual garantiza tiempo lineal esperado, y además también particiona los datos, quedando el n-ésimo elemento ordenado en su posición correspondiente Es implícito pero no requerido que este se base en el algoritmo de Hoare (o alguna variante) por sus requerimientos de tiempo lineal esperado y particionamiento de los datos.​​

Para Perl, el módulo Sort::Key::Top, disponible en CPAN, proporciona un conjunto de funciones para seleccionar los n primeros elementos de una lista usando múltiples ordenamientos y procedimientos de extracción de llaves. Además, el módulo Statistics::CaseResampling proporciona una función para calcular los cuantiles usando quickselect.

La biblioteca estándar de Python (desde 2.4) incluye heapq.nsmallest() and nlargest(), retornar listas ordenadas, en un principio en tiempo O(n + k log n), luego en O(n log k).

Véase también

• Optimización ordinal

Referencias

• Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). "Time bounds for selection". Journal of Computer and System Sciences 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.
• Floyd, R. W.; Rivest, R. L. (March 1975). "Expected time bounds for selection". Communications of the ACM 18 (3): 165–172. doi:10.1145/360680.360691.
• Kiwiel, K. C. (2005). "On Floyd and Rivest's SELECT algorithm". Theoretical Computer Science 347: 214–238. doi:10.1016/j.tcs.2005.06.032.
• 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.

Enlaces externos

• "Lecture notes for January 25, 1996: Selection and order statistics", ICS 161: Design and Analysis of Algorithms, David Eppstein

• Datos: Q3252726

KÑ