Selección rápida

En informática , quickselect es un algoritmo de selección para encontrar el k ésimo elemento más pequeño en una lista desordenada, también conocido como estadística de orden k ésimo . Al igual que el algoritmo de ordenamiento relacionado quicksort , fue desarrollado por Tony Hoare y, por lo tanto, también se lo conoce como algoritmo de selección de Hoare . ^[1] Al igual que quicksort, es eficiente en la práctica y tiene un buen rendimiento en el caso promedio, pero tiene un rendimiento deficiente en el peor de los casos. Quickselect y sus variantes son los algoritmos de selección que se utilizan con más frecuencia en implementaciones eficientes del mundo real.

Quickselect utiliza el mismo enfoque general que quicksort, eligiendo un elemento como pivote y dividiendo los datos en dos según el pivote, según si son menores o mayores que el pivote. Sin embargo, en lugar de recurrir a ambos lados, como en quicksort, quickselect solo recurre a un lado: el lado con el elemento que está buscando. Esto reduce la complejidad promedio de a , con un peor caso de . $O(n\log n)$ $O(n)$ $O(n^{2})$

Al igual que con quicksort, quickselect se implementa generalmente como un algoritmo in situ y, además de seleccionar el elemento $k$ , también ordena parcialmente los datos. Consulte el algoritmo de selección para obtener más información sobre la conexión con la ordenación.

Algoritmo

En quicksort, hay un subprocedimiento llamado partitionque puede, en tiempo lineal, agrupar una lista (que va desde los índices lefthasta right) en dos partes: aquellas menores que un elemento determinado y aquellas mayores o iguales que el elemento. Aquí hay un pseudocódigo que realiza una partición sobre el elemento list[pivotIndex]:

La función partición (lista, izquierda, derecha, índicePivote) es valorPivot := lista[índicePivot] Intercambiar lista[pivotIndex] y lista[right] // Mover el pivote al final storeIndex := izquierda para i de izquierda a derecha − 1 hacer  si lista[i] < pivotValue entonces Intercambiar lista[storeIndex] y lista[i] Incrementar índice de tienda Intercambia lista[derecha] y lista[storeIndex] // Mueve el pivote a su lugar final  devuelve storeIndex

Esto se conoce como el esquema de partición de Lomuto , que es más simple pero menos eficiente que el esquema de partición original de Hoare .

En quicksort, ordenamos recursivamente ambas ramas, lo que nos lleva al mejor momento . Sin embargo, al hacer la selección, ya sabemos en qué partición se encuentra nuestro elemento deseado, ya que el pivote está en su posición ordenada final, con todos los que lo preceden en un orden desordenado y todos los que lo siguen en un orden desordenado. Por lo tanto, una única llamada recursiva ubica el elemento deseado en la partición correcta, y nos basamos en esto para la selección rápida: $O(n\log n)$

// Devuelve el k-ésimo elemento más pequeño de la lista dentro de izquierda..derecha inclusive // (es decir, izquierda <= k <= derecha). function select(list, left, right, k) es  si izquierda = derecha entonces  // Si la lista contiene solo un elemento,  devuelve list[left] // devuelve ese elemento pivotIndex := ... // selecciona un pivotIndex entre izquierda y derecha,  // por ejemplo, izquierda + piso(rand() % (derecha − izquierda + 1)) pivotIndex := partición(lista, izquierda, derecha, pivotIndex) // El pivote está en su posición ordenada final  si k = pivotIndex entonces  devuelve list[k] de lo contrario si k < pivotIndex entonces  devuelve select(list, left, pivotIndex − 1, k) de lo contrario  devuelve select(list, pivotIndex + 1, right, k)

Tenga en cuenta la similitud con quicksort: así como el algoritmo de selección basado en mínimos es un ordenamiento por selección parcial, este es un quicksort parcial, que genera y particiona solo sus particiones. Este procedimiento simple tiene el rendimiento lineal esperado y, al igual que quicksort, tiene un rendimiento bastante bueno en la práctica. También es un algoritmo in situ , que solo requiere una sobrecarga de memoria constante si está disponible la optimización de llamadas de cola o si se elimina la recursión de cola con un bucle: $O(\log n)$ $O(n)$

La función select(lista, izquierda, derecha, k) es  un bucle  si izquierda = derecha entonces  devuelve lista[izquierda] pivotIndex := ... // selecciona pivotIndex entre izquierda y derecha pivotIndex := partición(lista, izquierda, derecha, pivotIndex) si k = pivotIndex entonces  devuelve lista[k] de lo contrario si k < pivotIndex entonces derecha := pivotIndex − 1 demás izquierda := pivotIndex + 1

Complejidad temporal

Al igual que quicksort, quickselect tiene un buen rendimiento promedio, pero es sensible al pivote que se elige. Si se eligen buenos pivotes, es decir, aquellos que disminuyen consistentemente el conjunto de búsqueda en una fracción dada, entonces el conjunto de búsqueda disminuye en tamaño exponencialmente y por inducción (o sumando la serie geométrica ) se ve que el rendimiento es lineal, ya que cada paso es lineal y el tiempo total es una constante multiplicada por esto (dependiendo de qué tan rápido se reduce el conjunto de búsqueda). Sin embargo, si se eligen malos pivotes consistentemente, como disminuir solo en un elemento cada vez, entonces el rendimiento en el peor de los casos es cuadrático: esto ocurre, por ejemplo, al buscar el elemento máximo de un conjunto, utilizando el primer elemento como pivote y habiendo ordenado los datos. Sin embargo, para pivotes elegidos aleatoriamente, este peor caso es muy poco probable: la probabilidad de usar más de comparaciones, para cualquier constante suficientemente grande , es superexponencialmente pequeña como una función de . ^[2] $O(n^{2}).$ ${\estilo de visualización Cn}$ ${\estilo de visualización C}$ ${\estilo de visualización C}$

Variantes

La solución más sencilla es elegir un pivote aleatorio, que produce un tiempo lineal casi seguro . De manera determinista, se puede utilizar la estrategia de pivote de mediana de 3 (como en la ordenación rápida), que produce un rendimiento lineal en datos parcialmente ordenados, como es habitual en el mundo real. Sin embargo, las secuencias artificiales pueden seguir provocando una complejidad del peor caso posible; David Musser describe una secuencia "asesina de mediana de 3" que permite un ataque contra esa estrategia, que fue una de las motivaciones para su algoritmo de introselect .

Se puede asegurar un rendimiento lineal incluso en el peor de los casos utilizando una estrategia de pivote más sofisticada; esto se hace en el algoritmo de mediana de medianas . Sin embargo, la sobrecarga de calcular el pivote es alta y, por lo tanto, esto generalmente no se usa en la práctica. Se puede combinar la selección rápida básica con la mediana de medianas como respaldo para obtener un rendimiento rápido en el caso promedio y un rendimiento lineal en el peor de los casos; esto se hace en introselect .

Los cálculos más finos de la complejidad temporal promedio producen un peor caso de para pivotes aleatorios (en el caso de la mediana; los otros k son más rápidos). ^[3] La constante se puede mejorar a 3/2 mediante una estrategia de pivote más complicada, lo que produce el algoritmo Floyd-Rivest , que tiene una complejidad promedio de para la mediana, siendo los otros k más rápidos. $n(2+2\log 2+o(1))\leq 3.4n+o(n)$ $1,5n+O(n^{1/2})$

Véase también

Referencias

^ Hoare, CAR (1961). "Algoritmo 65: Encontrar". Comm. ACM . 4 (7): 321–322. doi :10.1145/366622.366647.
^ 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. MR 0761047. Devroye, Luc (2001). "Sobre el peor momento probabilístico de 'find'" (PDF) . Algorithmica . 31 (3): 291–303. doi :10.1007/s00453-001-0046-2. MR 1855252.
^ Análisis al estilo Blum de Quickselect, David Eppstein , 9 de octubre de 2007.

Enlaces externos

"qselect", algoritmo de selección rápida en Matlab, Manolis Lourakis