Algoritmo de selección

Método para encontrar el k-ésimo valor más pequeño

En informática , un algoritmo de selección es un algoritmo para encontrar el enésimo valor más pequeño en una colección de valores ordenados, como números. El valor que encuentra se llama estadístico de décimo orden . La selección incluye como casos especiales los problemas de encontrar el elemento mínimo , mediano y máximo en la colección. Los algoritmos de selección incluyen la selección rápida y el algoritmo de mediana de medianas . Cuando se aplican a una colección de valores, estos algoritmos toman tiempo lineal , expresado mediante notación O grande . Para datos que ya están estructurados, es posible que sean posibles algoritmos más rápidos; Como caso extremo, la selección en una matriz ya ordenada lleva tiempo . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

Planteamiento del problema

Un algoritmo para el problema de selección toma como entrada una colección de valores y un número . ${\displaystyle k}$Genera el enésimo más pequeño de estos valores o, en algunas versiones del problema, una colección de los valores más pequeños. Para que esto esté bien definido, debería ser posible ordenar los valores de menor a mayor; por ejemplo, pueden ser números enteros , números de punto flotante o algún otro tipo de objeto con una clave numérica. Sin embargo, no se supone que ya hayan sido ordenados. A menudo, los algoritmos de selección están restringidos a un modelo de cálculo basado en comparación , como en los algoritmos de clasificación por comparación , donde el algoritmo tiene acceso a una operación de comparación que puede determinar el orden relativo de dos valores cualesquiera, pero no puede realizar ningún otro tipo de aritmética . operaciones sobre estos valores. ^[1] ${\displaystyle k}$ ${\displaystyle k}$

Para simplificar el problema, algunos trabajos sobre este problema suponen que todos los valores son distintos entre sí , ^[2] o que se ha utilizado algún método de desempate consistente para asignar un orden a pares de elementos con el mismo valor entre sí. . Otra variación en la definición del problema tiene que ver con la numeración de los valores ordenados: es el valor más pequeño que se obtiene estableciendo , como ${\displaystyle k=0}$ en la numeración de matrices basada en cero , o se obtiene configurando , siguiendo ${\displaystyle k=1}$ las convenciones habituales en inglés para el segundo más pequeño. -¿el más pequeño, etc.? Este artículo sigue las convenciones utilizadas por Cormen et al., según las cuales todos los valores son distintos y el valor mínimo se obtiene de . ^[2] ${\displaystyle k=1}$

Con estas convenciones, el valor máximo, entre una colección de valores, se obtiene estableciendo . Cuando es un número impar , la mediana de la colección se obtiene estableciendo . Cuando es par, hay dos opciones para la mediana, que se obtienen redondeando esta elección hacia abajo o hacia arriba, respectivamente: la mediana inferior con y la mediana superior con . ^[2] ${\displaystyle n}$ ${\displaystyle k=n}$ ${\displaystyle n}$ ${\displaystyle k=(n+1)/2}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$ ${\displaystyle k=n/2+1}$

Algoritmos

Ordenar y seleccionar en montón

Como algoritmo de referencia, la selección del enésimo valor más pequeño de una colección de valores se puede realizar mediante los dos pasos siguientes: ${\displaystyle k}$

• Ordenar la colección
• Si la salida del algoritmo de clasificación es una matriz , recupere su enésimo elemento; de lo contrario, escanee la secuencia ordenada para encontrar el enésimo elemento. ${\displaystyle k}$ ${\displaystyle k}$

El tiempo de este método está dominado por el paso de clasificación, que requiere tiempo mediante una clasificación por comparación . ^{[2] [3]} Incluso cuando se pueden usar algoritmos de clasificación de enteros , estos generalmente son más lentos que el tiempo lineal que se puede lograr usando algoritmos de selección especializados. Sin embargo, la simplicidad de este enfoque lo hace atractivo, especialmente cuando se proporciona una rutina de clasificación altamente optimizada como parte de una biblioteca en tiempo de ejecución, pero no un algoritmo de selección. Para entradas de tamaño moderado, la clasificación puede ser más rápida que los algoritmos de selección no aleatoria, debido a los factores constantes más pequeños en su tiempo de ejecución. ^[4] Este método también produce una versión ordenada de la colección, que puede ser útil para otros cálculos posteriores y, en particular, para la selección con otras opciones de . ^[3] ${\displaystyle \Theta (n\log n)}$ ${\displaystyle k}$

Para un algoritmo de clasificación que genera un elemento a la vez, como la clasificación por selección , el escaneo se puede realizar en conjunto con la clasificación, y la clasificación se puede finalizar una vez que se haya encontrado el ésimo elemento. Un posible diseño de un grupo de consolación en un torneo de eliminación simple , en el que los equipos que perdieron ante el eventual ganador juegan otro minitorneo para determinar el segundo lugar, puede verse como un ejemplo de este método. ^[5] La aplicación de esta optimización a heapsort produce el algoritmo heapselect , que puede seleccionar el enésimo valor más pequeño en el tiempo . ^[6] Esto es rápido cuando es pequeño en relación con , pero degenera para valores más grandes de , como la elección utilizada para encontrar la mediana. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(n+k\log n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$

Pivotando

Muchos métodos de selección se basan en elegir un elemento "pivote" especial de la entrada y usar comparaciones con este elemento para dividir los valores de entrada restantes en dos subconjuntos: el conjunto de elementos menores que el pivote y el conjunto de elementos mayores que el pivote. Luego, el algoritmo puede determinar dónde se puede encontrar el valor más pequeño, basándose en una comparación con los tamaños de estos conjuntos. En particular, si , el valor más pequeño está en , y se puede encontrar de forma recursiva aplicando el mismo algoritmo de selección a . Si es , entonces el valor más pequeño es el pivote y se puede devolver inmediatamente. En el caso restante, el valor más pequeño está en , y más concretamente es el elemento en posición de . Se puede encontrar aplicando un algoritmo de selección de forma recursiva, buscando el valor en esta posición en . ^[7] ${\displaystyle n-1}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\leq |L|}$ ${\displaystyle k}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle k=|L|+1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle k-|L|-1}$ ${\displaystyle R}$ ${\displaystyle R}$

Al igual que con el algoritmo de clasificación rápida basado en pivote relacionado , la partición de la entrada en y se puede realizar creando nuevas colecciones para estos conjuntos, o mediante un método que particione una lista o un tipo de datos de matriz determinados en el lugar. Los detalles varían dependiendo de cómo se representa la colección de entrada. ^[8] El tiempo para comparar el pivote con todos los demás valores es . ^[7] Sin embargo, los métodos de pivote difieren en cómo eligen el pivote, lo que afecta el tamaño de los subproblemas en cada llamada recursiva. La eficacia de estos métodos depende en gran medida de la elección del pivote. Si el pivote se elige mal, el tiempo de ejecución de este método puede ser tan lento como . ^[4] ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

• Si el pivote estuviera exactamente en la mediana de la entrada, entonces cada llamada recursiva tendría como máximo la mitad de valores que la llamada anterior, y los tiempos totales se sumarían en una serie geométrica a . ${\displaystyle O(n)}$Sin embargo, encontrar la mediana es en sí mismo un problema de selección de toda la entrada original. Intentar encontrarlo mediante una llamada recursiva a un algoritmo de selección conduciría a una recursión infinita, porque el tamaño del problema no disminuiría en cada llamada. ^[7]
• Quickselect elige el pivote de manera uniforme y aleatoria a partir de los valores de entrada. Puede describirse como un algoritmo de poda y búsqueda , ^[9] una variante de Quicksort , con la misma estrategia de pivote, pero donde Quicksort realiza dos llamadas recursivas para ordenar las dos subcolecciones y Quickselect solo realiza una de estas dos llamadas. Su hora prevista es . ^{[2] [7] [9]} Para cualquier constante , la probabilidad de que su número de comparaciones exceda es superexponencialmente pequeña en . ^[10] ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle C}$ ${\displaystyle Cn}$ ${\displaystyle C}$
• El algoritmo Floyd-Rivest , una variación de la selección rápida, elige un pivote muestreando aleatoriamente un subconjunto de valores de datos, para algún tamaño de muestra , y luego seleccionando recursivamente dos elementos algo por encima y por debajo de la posición de la muestra para usarlos como pivotes. Con esta elección, es probable que quede intercalado entre los dos pivotes, de modo que después de pivotar solo quede una pequeña cantidad de valores de datos entre los pivotes para una llamada recursiva. Este método puede lograr un número esperado de comparaciones, es decir . ^[11] En su trabajo original, Floyd y Rivest afirmaron que el término podría hacerse tan pequeño como mediante un esquema de muestreo recursivo, pero se ha cuestionado la exactitud de su análisis. ^{[12] [13]} En cambio, un análisis más riguroso ha demostrado que una versión de su algoritmo logra este término. ^[14] Aunque el análisis habitual tanto de la selección rápida como del algoritmo Floyd-Rivest supone el uso de un generador de números aleatorios verdadero , se ha demostrado una versión del algoritmo Floyd-Rivest que utiliza un generador de números pseudoaleatorios sembrado solo logarítmicamente con muchos bits aleatorios verdaderos. ejecutarse en tiempo lineal con alta probabilidad. ^[15] ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle rk/n}$ ${\displaystyle k}$ ${\displaystyle n+\min(k,n-k)+o(n)}$ ${\displaystyle o(n)}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n\log n}})}$

Visualización de la selección de pivotes para el método de mediana de medianas . Cada conjunto de cinco elementos se muestra como una columna de puntos en la figura, ordenados en orden creciente de arriba a abajo. Si sus medianas (los puntos verdes y morados en la fila del medio) se ordenan en orden creciente de izquierda a derecha, y se elige la mediana de las medianas como pivote, entonces los elementos en el cuadrante superior izquierdo serán menores que el pivote, y los elementos en el cuadrante inferior derecho serán mayores que el pivote, lo que demuestra que muchos elementos se eliminarán al pivotar. ${\displaystyle 3n/10}$ ${\displaystyle 3n/10}$

• El método de mediana de medianas divide la entrada en conjuntos de cinco elementos y utiliza algún otro método no recursivo para encontrar la mediana de cada uno de estos conjuntos en tiempo constante por conjunto. Luego se llama a sí mismo de forma recursiva para encontrar la mediana de estas medianas. Usar la mediana resultante de medianas como pivote produce una partición con . Por lo tanto, un problema sobre elementos se reduce a dos problemas recursivos sobre elementos (para encontrar el pivote) y como máximo elementos (después de usar el pivote). El tamaño total de estos dos subproblemas recursivos es como máximo , lo que permite analizar el tiempo total como una serie geométrica que se suma a . A diferencia de la selección rápida, este algoritmo es determinista, no aleatorio. ^{[2] [4] [5]} Fue el primer algoritmo de selección determinista de tiempo lineal conocido, ^[5] y se enseña comúnmente en clases de algoritmos de pregrado como un ejemplo de divide y vencerás que no se divide en dos subproblemas iguales. ^{[2] [4] [9] [16]} Sin embargo, los altos factores constantes en su límite de tiempo lo hacen más lento que la selección rápida en la práctica, ^{[3] [9]} e incluso más lento que la clasificación para entradas de tamaño moderado. ^[4] ${\displaystyle n/5}$ ${\displaystyle \max(|L|,|R|)\leq 7n/10}$ ${\displaystyle n}$ ${\displaystyle n/5}$ ${\displaystyle 7n/10}$ ${\displaystyle 9n/10}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$
• Se pueden utilizar algoritmos híbridos como la introselect para lograr el rendimiento práctico de la selección rápida con un recurso a las medianas de las medianas que garantizan el peor de los casos . ^[17] ${\displaystyle O(n)}$

Fábricas

Los algoritmos de selección deterministas con el menor número de comparaciones conocido, para valores de que están lejos de o , se basan en el concepto de fábricas , introducido en 1976 por Arnold Schönhage , Mike Paterson y Nick Pippenger . ^[18] Estos son métodos que construyen órdenes parciales de ciertos tipos específicos, en pequeños subconjuntos de valores de entrada, mediante el uso de comparaciones para combinar órdenes parciales más pequeñas. Como ejemplo muy simple, un tipo de fábrica puede tomar como entrada una secuencia de pedidos parciales de un solo elemento, comparar pares de elementos de estos pedidos y producir como salida una secuencia de conjuntos totalmente ordenados de dos elementos. Los elementos utilizados como insumos para esta fábrica podrían ser valores de insumos que aún no se han comparado con nada o valores "de desecho" producidos por otras fábricas. El objetivo de un algoritmo basado en fábricas es combinar diferentes fábricas, con las salidas de algunas fábricas yendo a las entradas de otras, para eventualmente obtener un orden parcial en el que un elemento (el enésimo más pequeño ) es más grande que algún otro. elementos y más pequeño que otros. Un diseño cuidadoso de estas fábricas conduce a un algoritmo que, cuando se aplica a la búsqueda de la mediana, utiliza en la mayoría de las comparaciones. Para otros valores de , el número de comparaciones es menor. ^[19] ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle n-k}$ ${\displaystyle 2.942n}$ ${\displaystyle k}$

Algoritmos paralelos

Los algoritmos paralelos de selección se han estudiado desde 1975, cuando Leslie Valiant introdujo el modelo de árbol de comparación paralelo para analizar estos algoritmos, y demostró que en este modelo la selección utilizando un número lineal de comparaciones requiere pasos paralelos, incluso para seleccionar el mínimo o el máximo. ^[20] Posteriormente, los investigadores encontraron algoritmos paralelos para la selección en pasos, que coincidían con este límite. ^{[21] [22]} En un modelo de árbol de comparación paralelo aleatorio es posible realizar la selección en un número limitado de pasos y un número lineal de comparaciones. ^[23] En el modelo de computación RAM paralelo más realista , con acceso exclusivo a la memoria de lectura y escritura exclusiva, la selección se puede realizar en el tiempo con los procesadores, lo cual es óptimo tanto en el tiempo como en el número de procesadores. ^[24] Con el acceso concurrente a la memoria, en general es posible un tiempo paralelo ligeramente más rápido, ^[25] y el término en el límite de tiempo puede reemplazarse por . ^[26] ${\displaystyle \Omega (\log \log n)}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n/\log n)}$ ${\displaystyle \log n}$ ${\displaystyle \log k}$

Estructuras de datos sublineales

Cuando los datos ya están organizados en una estructura de datos , es posible realizar una selección en un período de tiempo sublineal en el número de valores. Como un caso simple de esto, para los datos ya ordenados en una matriz, la selección del elemento ésimo se puede realizar mediante una única búsqueda en la matriz, en tiempo constante. ^[27] Para valores organizados en una matriz bidimensional de tamaño , con filas y columnas ordenadas, la selección se puede realizar en el tiempo , o más rápido cuando es pequeño en relación con las dimensiones de la matriz. ^{[27] [28]} Para una colección de matrices ordenadas unidimensionales, con elementos menores que el elemento seleccionado en la enésima matriz, el tiempo es . ^[28] ${\displaystyle k}$ ${\displaystyle m\times n}$ ${\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$

La selección de datos en un montón binario lleva tiempo . ${\displaystyle O(k)}$Esto es independiente del tamaño del montón y más rápido que el límite de tiempo que se obtendría con la búsqueda "mejor primero" . ^{[28] [29]} Este mismo método se puede aplicar de manera más general a datos organizados como cualquier tipo de árbol ordenado en montón (un árbol en el que cada nodo almacena un valor en el que el padre de cada nodo no raíz tiene un valor menor que su hijo). Este método de realizar la selección en un montón se ha aplicado a problemas de enumerar múltiples soluciones a problemas de optimización combinatoria, como encontrar los k caminos más cortos en un gráfico ponderado, definiendo un espacio de estados de soluciones en forma de un montón definido implícitamente. árbol ordenado, y luego aplicar este algoritmo de selección a este árbol. ^[30] En la otra dirección, se han utilizado algoritmos de selección de tiempo lineal como subrutina en una estructura de datos de cola de prioridad relacionada con el montón, mejorando el tiempo para extraer su ésimo elemento de a ; aquí está el logaritmo iterado . ^[31] ${\displaystyle n}$ ${\displaystyle O(k\log n)}$ ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log ^{*}n+\log k)}$ ${\displaystyle \log ^{*}n}$

Para una colección de valores de datos que se someten a inserciones y eliminaciones dinámicas, el árbol de estadísticas de orden aumenta una estructura de árbol de búsqueda binaria autoequilibrada con una cantidad constante de información adicional por nodo del árbol, lo que permite inserciones, eliminaciones y consultas de selección que solicitan el elemento ésimo . en el conjunto actual para que todos se realicen a tiempo por operación. ^[2] Yendo más allá del modelo de comparación de cálculo, son posibles tiempos más rápidos por operación para valores que son números enteros pequeños, en los que se permiten operaciones aritméticas binarias. ^[32] No es posible que un algoritmo de transmisión con memoria sublineal en ambos y resuelva consultas de selección exactamente para datos dinámicos, pero el esquema de conteo mínimo se puede usar para resolver consultas de selección aproximadamente, encontrando un valor cuya posición en el orden de los elementos (si se les agregara) estaría dentro de pasos de , para un boceto cuyo tamaño está dentro de factores logarítmicos de . ^[33] ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon n}$ ${\displaystyle k}$ ${\displaystyle 1/\varepsilon }$

límites inferiores

El tiempo de ejecución de los algoritmos de selección descritos anteriormente es necesario, porque un algoritmo de selección que puede manejar entradas en un orden arbitrario debe tomar ese mismo tiempo para examinar todas sus entradas. Si alguno de sus valores de entrada no se compara, ese valor podría ser el que debería haberse seleccionado y se puede hacer que el algoritmo produzca una respuesta incorrecta. ^[28] Más allá de este simple argumento, se ha realizado una cantidad significativa de investigaciones sobre el número exacto de comparaciones necesarias para la selección, tanto en los casos aleatorios como en los deterministas. ${\displaystyle O(n)}$

Seleccionar el mínimo de valores requiere comparaciones, porque se debe haber determinado que los valores que no se seleccionan no son mínimos, al ser los más grandes en alguna comparación, y no hay dos de estos valores que puedan ser los más grandes en la misma comparación. El mismo argumento se aplica simétricamente a la selección del máximo. ^[14] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

El siguiente caso más simple es seleccionar el segundo más pequeño. Después de varios intentos incorrectos, el primer límite inferior estricto de este caso fue publicado en 1964 por el matemático soviético Sergey Kislitsyn . Se puede demostrar observando que seleccionar el segundo valor más pequeño también requiere distinguir el valor más pequeño del resto, y considerando el número de comparaciones que involucran el valor más pequeño que realiza un algoritmo para este problema. Cada uno de los elementos que se compararon con el valor más pequeño es candidato para el segundo más pequeño, y de estos valores se debe encontrar mayor que otro valor en una segunda comparación para descartarlos como el segundo más pequeño. Si los valores son mayores en al menos una comparación y los valores son mayores en al menos dos comparaciones, hay un total de al menos comparaciones. Un argumento adversario , en el que el resultado de cada comparación se elige para maximizar (sujeto a la coherencia con al menos un orden posible) en lugar de por los valores numéricos de los elementos dados, muestra que es posible forzar a que sea al menos . Por lo tanto, el número de comparaciones necesarias en el peor de los casos para seleccionar el segundo más pequeño es , el mismo número que se obtendría si se celebrara un torneo de eliminación simple con un torneo de segunda vuelta entre los valores que perdieron ante el valor más pequeño. Sin embargo, el número esperado de comparaciones de un algoritmo de selección aleatoria puede ser mejor que este límite; por ejemplo, seleccionar el segundo elemento más pequeño de seis elementos requiere siete comparaciones en el peor de los casos, pero puede realizarse mediante un algoritmo aleatorio con un número esperado de 6,5 comparaciones. ^[14] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle n-1}$ ${\displaystyle p-1}$ ${\displaystyle n+p-2}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \log _{2}n}$ ${\displaystyle n+\lceil \log _{2}n\rceil -2}$

De manera más general, seleccionar el elemento número uno requiere al menos comparaciones; en el caso promedio, hacer coincidir el número de comparaciones del algoritmo Floyd-Rivest hasta su término. El argumento se hace directamente a favor de los algoritmos deterministas, con un número de comparaciones que se promedia sobre todas las permutaciones posibles de los valores de entrada. ^[1] Según el principio de Yao , también se aplica al número esperado de comparaciones para un algoritmo aleatorio en su entrada del peor de los casos. ^[34] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n+\min(k,n-k)-O(1)}$ ${\displaystyle o(n)}$

Para algoritmos deterministas, se ha demostrado que seleccionar el elemento ésimo requiere comparaciones, donde ${\displaystyle k}$ ${\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}$

$${\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}$$

función de entropía binaria . ^[35]al menos ${\displaystyle (2+\varepsilon )n}$. ^[36] ${\displaystyle \varepsilon \approx 2^{-80}}$

Números exactos de comparaciones

Encontrar la mediana de cinco valores usando seis comparaciones. Cada paso muestra las comparaciones que se realizarán a continuación como segmentos de línea amarilla y un diagrama de Hasse de las relaciones de orden encontradas hasta ahora (con menor=inferior y mayor=superior) como segmentos de línea azul. Ya se ha descubierto que los elementos rojos son mayores que otros tres y, por lo tanto, no pueden ser la mediana. El mayor de los dos elementos en la comparación final es la mediana.

Knuth proporciona el siguiente triángulo de números que resumen pares de y para los cuales se conoce el número exacto de comparaciones necesarias para un algoritmo de selección óptimo. La enésima fila del triángulo (comenzando en la fila superior) proporciona el número de comparaciones para entradas de valores, y el enésimo número dentro de cada fila proporciona el número de comparaciones necesarias para seleccionar el enésimo valor más pequeño de una entrada de ese tamaño. Las filas son simétricas porque seleccionar la enésima más pequeña requiere exactamente el mismo número de comparaciones, en el peor de los casos, que seleccionar la enésima más grande. ^[14] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

0

1 1

2 3 2

3 4 4 3

4 6 6 6 4

5 7 8 8 7 5

6 8 10 10 10 8 6

7 9 11 12 12 11 9 7

8 11 12 14 14 14 12 11 8

9 12 14 15 16 16 15 14 12 9

La mayoría, pero no todas, las entradas en la mitad izquierda de cada fila se pueden encontrar usando la fórmula

$${\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}$$

Milton Sobeldécimo^{[14] [37][14] [38]} ${\displaystyle k}$

Ayuda de idioma

Muy pocos idiomas tienen soporte incorporado para la selección general, aunque muchos brindan funciones para encontrar el elemento más pequeño o más grande de una lista. Una excepción notable es la Biblioteca de plantillas estándar para C++ , que proporciona un nth_elementmétodo basado en plantilla con una garantía del tiempo lineal esperado. ^[3]

La biblioteca estándar de Pythonheapq.nsmallest (desde 2.4) incluye subrutinas heapq.nlargestpara devolver los elementos más pequeños o más grandes de una colección, en orden. Diferentes versiones de Python han utilizado diferentes algoritmos para estas subrutinas. A partir de la versión 3.13 de Python, la implementación mantiene un montón binario, limitado a contener elementos e inicializado con los primeros elementos de la colección. Luego, cada elemento posterior de la colección puede reemplazar el elemento más grande o más pequeño en el montón (respectivamente para y ) si es más pequeño o más grande que este elemento. El peor momento para esta implementación es peor que el que se lograría con heapselect. Sin embargo, para secuencias de entrada aleatorias, es probable que haya pocas actualizaciones del montón y la mayoría de los elementos de entrada se procesan con una sola comparación. ^[39] ${\displaystyle k}$ ${\displaystyle k}$heapq.nsmallestheapq.nlargest ${\displaystyle O(n\log k)}$ ${\displaystyle O(n+k\log n)}$

Desde 2017, Matlab ha incluido funciones maxk()y mink()que devuelven los valores máximos (mínimos) en un vector, así como sus índices. La documentación de Matlab no especifica qué algoritmo utilizan estas funciones ni cuál es su tiempo de ejecución. ^[40] ${\displaystyle k}$

Historia

Quickselect fue presentado sin análisis por Tony Hoare en 1965, ^[41] y analizado por primera vez en un informe técnico de 1971 por Donald Knuth . ^[11] El primer algoritmo de selección determinista de tiempo lineal conocido es el método de mediana de medianas , publicado en 1973 por Manuel Blum , Robert W. Floyd , Vaughan Pratt , Ron Rivest y Robert Tarjan . ^[5] Rastrean la formulación del problema de selección hasta el trabajo de Charles L. Dodgson (más conocido como Lewis Carroll ), quien en 1883 señaló que el diseño habitual de los torneos deportivos de eliminación simple no garantiza que gane el segundo mejor jugador. segundo lugar, ^{[5] [42]} y al trabajo de Hugo Steinhaus alrededor de 1930, quien siguió esta misma línea de pensamiento al pedir un diseño de torneo que pueda ofrecer esta garantía, con un número mínimo de juegos jugados (es decir, comparaciones ). ^[5]

Ver también

• Mediana geométrica § Computación , algoritmos para generalizaciones de medianas de dimensiones superiores
• Filtro de mediana , aplicación de algoritmos de búsqueda de mediana en el procesamiento de imágenes.

Referencias

1. Cunto, Walter; Munro, J. Ian (1989). "Selección de casos promedio". Revista de la ACM . 36 (2): 270–279. doi : 10.1145/62044.62047 . SEÑOR  1072421. S2CID  10947879.
2. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. "Capítulo 9: Medianas y estadísticas de orden". Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. págs. 213–227. ISBN 0-262-03384-4.; "Sección 14.1: Estadísticas de pedidos dinámicos", págs. 339–345
3. Skiena, Steven S. (2020). "17.3: Mediana y selección". El manual de diseño de algoritmos . Textos de Informática (Tercera ed.). Saltador. págs. 514–516. doi :10.1007/978-3-030-54256-6. ISBN 978-3-030-54255-9. SEÑOR  4241430. S2CID  22382667.
4. Erickson, Jeff (junio de 2019). "1.8: Selección de tiempo lineal". Algoritmos. págs. 35–39.
5. Blum, Manuel ; Floyd, Robert W .; Pratt, Vaughan ; Rivest, Ronald L .; Tarjan, Robert E. (1973). «Plazos de tiempo para la selección» (PDF) . Revista de Ciencias de la Computación y de Sistemas . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 . SEÑOR  0329916.
6. Brodal, Gerth Stølting (2013). "Una encuesta sobre colas prioritarias". En Brodnik, Andrej; López-Ortiz, Alejandro; Raman, Venkatesh; Viola, Alfredo (eds.). "Estructuras, flujos y algoritmos de datos eficientes en el espacio: artículos en honor a J. Ian Munro con motivo de su 66 cumpleaños ". Apuntes de conferencias sobre informática. vol. 8066. Saltador. págs. 150-163. doi :10.1007/978-3-642-40273-9_11.
7. Kleinberg, Jon ; Tardos, Éva (2006). "13.5 Divide y vencerás aleatoriamente: búsqueda de medianas y clasificación rápida". Diseño de algoritmos . Addison-Wesley. págs. 727–734. ISBN 9780321295354.
8. Por ejemplo, Cormen et al. use una partición de matriz in situ, mientras que Kleinberg y Tardos describen la entrada como un conjunto y usan un método que la divide en dos nuevos conjuntos.
9. Goodrich, Michael T .; Tamassia, Roberto (2015). "9.2: Selección". Diseño y aplicaciones de algoritmos . Wiley. págs. 270–275. ISBN 978-1-118-33591-8.
10. Devroye, Luc (1984). "Límites exponenciales para el tiempo de ejecución de un algoritmo de selección" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 29 (1): 1–7. doi :10.1016/0022-0000(84)90009-6. SEÑOR  0761047. Devroye, Luc (2001). "Sobre el peor momento probabilístico de 'hallazgo'" (PDF) . Algorítmica . 31 (3): 291–303. doi :10.1007/s00453-001-0046-2. SEÑOR  1855252. S2CID  674040.
11. Floyd, Robert W .; Rivest, Ronald L. (marzo de 1975). "Plazos de tiempo previstos para la selección". Comunicaciones de la ACM . 18 (3): 165-172. doi : 10.1145/360680.360691 . S2CID  3064709.Véase también "Algoritmo 489: el algoritmo SELECT, para encontrar el enésimo elemento más pequeño ", pág. 173, doi :10.1145/360680.360694. ${\displaystyle i}$ ${\displaystyle n}$
12. Brown, Theodore (septiembre de 1976). "Observación sobre el algoritmo 489". Transacciones ACM sobre software matemático . 2 (3): 301–304. doi :10.1145/355694.355704. S2CID  13985011.
13. Postmo, JT; Rinnooy Kan, AHG ; Timmer, GT (1983). "Un método de selección dinámico eficiente". Comunicaciones de la ACM . 26 (11): 878–881. doi : 10.1145/182.358440 . SEÑOR  0784120. S2CID  3211474.
14. Knuth, Donald E. (1998). "Sección 5.3.3: Selección de comparación mínima". El arte de la programación informática, volumen 3: clasificación y búsqueda (2ª ed.). Addison-Wesley. págs. 207-219. ISBN 0-201-89685-0.
15. Karloff, Howard J.; Raghavan, Prabhakar (1993). "Algoritmos aleatorios y números pseudoaleatorios". Revista de la ACM . 40 (3): 454–476. doi : 10.1145/174130.174132 . SEÑOR  1370358. S2CID  17956460.
16. Gurwitz, Chaya (1992). "Sobre la enseñanza de algoritmos de búsqueda de medianas". Transacciones IEEE sobre educación . 35 (3): 230–232. Código Bib : 1992ITEdu..35..230G. doi :10.1109/13.144650.
17. Musser, David R. (agosto de 1997). "Algoritmos introspectivos de clasificación y selección". Software: práctica y experiencia . Wiley. 27 (8): 983–993. doi :10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-#.
18. Schönhage, A .; Paterson, M .; Pippenger, N. (1976). "Encontrar la mediana". Revista de Ciencias de la Computación y de Sistemas . 13 (2): 184-199. doi :10.1016/S0022-0000(76)80029-3. SEÑOR  0428794. S2CID  29867292.
19. Dor, Dorit ; Zwick, Uri (1999). "Seleccionar la mediana". Revista SIAM de Computación . 28 (5): 1722-1758. doi :10.1137/S0097539795288611. SEÑOR  1694164. S2CID  2633282.
20. Valiente, Leslie G. (1975). "Paralelismo en problemas de comparación". Revista SIAM de Computación . 4 (3): 348–355. doi :10.1137/0204030. SEÑOR  0378467.
21. Ajtai, Miklós ; Komlós, János ; Steiger, WL; Szemerédi, Endre (1989). "La selección paralela óptima tiene complejidad ". Revista de Ciencias de la Computación y de Sistemas . 38 (1): 125-133. doi :10.1016/0022-0000(89)90035-4. SEÑOR  0990052. ${\displaystyle O(\log \log n)}$
22. Azar, Yossi; Pippenger, Nicolás (1990). "Selección paralela". Matemática Aplicada Discreta . 27 (1–2): 49–58. doi :10.1016/0166-218X(90)90128-Y. SEÑOR  1055590.
23. Reischuk, Rüdiger (1985). "Algoritmos probabilísticos paralelos para ordenación y selección". Revista SIAM de Computación . 14 (2): 396–409. doi :10.1137/0214030. SEÑOR  0784745.
24. Han, Yijie (2007). "Selección paralela óptima". Transacciones ACM sobre algoritmos . 3 (4): A38:1–A38:11. doi :10.1145/1290672.1290675. SEÑOR  2364962. S2CID  9645870.
25. Chaudhuri, Shiva; Hagerup, Torben; Raman, Rajeev (1993). "Selección paralela determinista aproximada y exacta". En Borzyszkowski, Andrzej M.; Sokolowski, Stefan (eds.). Fundamentos matemáticos de la informática 1993, 18.º Simposio internacional, MFCS'93, Gdansk, Polonia, 30 de agosto - 3 de septiembre de 1993, Actas . Apuntes de conferencias sobre informática. vol. 711. Saltador. págs. 352–361. doi :10.1007/3-540-57182-5_27. hdl : 11858/00-001M-0000-0014-B748-C .
26. Dietz, Paul F.; Raman, Rajeev (1999). "Selección de rango pequeño en paralelo, con aplicaciones a la construcción de pilas". Revista de algoritmos . 30 (1): 33–51. doi :10.1006/jagm.1998.0971. SEÑOR  1661179.
27. Frederickson, Greg N.; Johnson, Donald B. (1984). "Selección y clasificación generalizada: matrices ordenadas". Revista SIAM de Computación . 13 (1): 14–30. doi :10.1137/0213002. SEÑOR  0731024.
28. Kaplan, Haim; Kozma, László; Zamir, o; Zwick, Uri (2019). "Selección de montones, matrices ordenadas por filas y uso de montones suaves". En Fineman, Jeremy T.; Mitzenmacher, Michael (eds.). Segundo Simposio sobre simplicidad en algoritmos, SOSA 2019, 8 al 9 de enero de 2019, San Diego, CA, EE. UU . OASics. vol. 69. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 5:1–5:21. arXiv : 1802.07041 . doi :10.4230/OASIcs.SOSA.2019.5. ${\displaystyle X+Y}$
29. Frederickson, Greg N. (1993). "Un algoritmo óptimo para la selección en un montón mínimo". Información y Computación . 104 (2): 197–214. doi : 10.1006/inco.1993.1030 . SEÑOR  1221889.
30. Eppstein, David (1999). "Encontrar los caminos más cortos". Revista SIAM de Computación . 28 (2): 652–673. doi :10.1137/S0097539795290477. SEÑOR  1634364. ${\displaystyle k}$
31. Babenko, Máxima; Kolesnichenko, Ignat; Smirnov, Iván (2019). "Montón en cascada: hacia extracciones en el tiempo óptimo". Teoría de los Sistemas Computacionales . 63 (4): 637–646. doi :10.1007/s00224-018-9866-1. SEÑOR  3942251. S2CID  253740380.
32. Pătraşcu, Mihai ; Thorup, Mikkel (2014). "Conjuntos de enteros dinámicos con clasificación, selección y búsqueda de predecesores óptimos". 55.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2014, Filadelfia, PA, EE. UU., 18 al 21 de octubre de 2014 . Sociedad de Computación IEEE. págs. 166-175. arXiv : 1408.3045 . doi :10.1109/FOCS.2014.26.
33. Cormode, Graham; Muthukrishnan, S. (2005). "Un resumen mejorado del flujo de datos: el boceto del conteo mínimo y sus aplicaciones". Revista de algoritmos . 55 (1): 58–75. doi :10.1016/j.jalgor.2003.12.001. SEÑOR  2132028.
34. Chan, Timothy M. (2010). "Límites inferiores de selección basados ​​en comparación espacio-temporal". Transacciones ACM sobre algoritmos . 6 (2): A26:1–A26:16. doi :10.1145/1721837.1721842. SEÑOR  2675693. S2CID  11742607.
35. Doblado, Samuel W.; Juan, Juan W. (1985). "Encontrar la mediana requiere comparaciones". En Sedgewick, Robert (ed.). Actas del 17º Simposio Anual de la ACM sobre Teoría de la Computación, 6 al 8 de mayo de 1985, Providence, Rhode Island, EE. UU . Asociación para Maquinaria de Computación. págs. 213-216. doi : 10.1145/22145.22169 . ${\displaystyle 2n}$
36. Dor, Dorit ; Zwick, Uri (2001). "La selección de la mediana requiere comparaciones". Revista SIAM de Matemática Discreta . 14 (3): 312–325. doi :10.1137/S0895480199353895. SEÑOR  1857348. ${\displaystyle (2+\varepsilon )N}$
37. Hadián, Abdollah; Sobel, Milton (mayo de 1969). Seleccionar el -ésimo más grande mediante comparaciones binarias sin errores (Informe). Informes Técnicos de la Escuela de Estadística. vol. 121. Universidad de Minnesota. hdl :11299/199105. ${\displaystyle t}$
38. Gasarch, William ; Kelly, Wayne; Pugh, William (julio de 1996). "Encontrar el décimo mayor para el pequeño ". Noticias ACM SIGACT . 27 (2): 88–96. doi :10.1145/235767.235772. S2CID  3133332. ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle i,n}$
39. "código fuente del paquete heapq". Biblioteca de Python . Consultado el 6 de agosto de 2023 .; consulte también la comparación vinculada del rendimiento del algoritmo en los datos del mejor de los casos.
40. "visón: encuentre k elementos más pequeños de la matriz". Documentación de Matlab R2023a . Trabajos de matemáticas . Consultado el 30 de marzo de 2023 .
41. Hoare, CAR (julio de 1961). "Algoritmo 65: Buscar". Comunicaciones de la ACM . 4 (7): 321–322. doi :10.1145/366622.366647.
42. Dodgson, Charles L. (1883). Torneos de tenis sobre césped: el verdadero método de asignación de premios con una prueba de la falacia del método actual . Londres: Macmillan and Co.Véase también Wilson, Robin; Moktefi, Amirouche, eds. (2019). "Torneos de tenis sobre hierba". El mundo matemático de Charles L. Dodgson (Lewis Carroll) . Prensa de la Universidad de Oxford. pag. 129.ISBN​ 9780192549013.