En informática , la selección rápida es un algoritmo de selección para encontrar el k- ésimo elemento más pequeño en una lista desordenada. Está relacionado con el algoritmo de clasificación rápida . Al igual que la clasificación rápida, fue desarrollado por Tony Hoare y, por lo tanto, también se conoce como el algoritmo de selección de Hoare . [1] Al igual que el ordenamiento rápido, es eficiente en la práctica y tiene un buen desempeño en el caso promedio, pero tiene un desempeño pobre en el peor de los casos. Quickselect y sus variantes son los algoritmos de selección más utilizados en implementaciones eficientes del mundo real.
Clase | Algoritmo de selección |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | О ( n 2 ) |
Rendimiento en el mejor de los casos | О ( n ) |
Rendimiento medio | O ( n ) |
Quickselect utiliza el mismo enfoque general que el ordenamiento rápido, eligiendo un elemento como pivote y dividiendo los datos en dos según el pivote, en consecuencia, como menor o mayor que el pivote. Sin embargo, en lugar de recurrir a ambos lados, como en el ordenamiento rápido, la selección rápida solo recurre a un lado: el lado con el elemento que está buscando. Esto reduce la complejidad promedio de a , con el peor de los casos .
Al igual que con la ordenación rápida, la selección rápida generalmente se implementa como un algoritmo in situ y, más allá de seleccionar el k- ésimo elemento, también ordena parcialmente los datos. Consulte el algoritmo de selección para obtener más información sobre la conexión con la clasificación.
Algoritmo
En quicksort, hay un subprocedimiento llamado partition
que puede, en tiempo lineal, agrupar una lista (que va desde índices left
hasta right
) en dos partes: los menores que un determinado elemento y los mayores o iguales al elemento. Aquí hay un pseudocódigo que realiza una partición sobre el elemento list[pivotIndex]
:
partición de función (lista, izquierda, derecha, pivotIndex) es pivotValue: = lista [pivotIndex] swap list [pivotIndex] y list [right] // Mover el pivote al final storeIndex: = izquierda para i de izquierda a derecha - 1 hacer si list [i]then lista de intercambio [storeIndex] y lista [i] incremento storeIndex swap list [derecha] y list [storeIndex] // Mover el pivote a su lugar final return 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 ordenación rápida, ordenamos de forma recursiva ambas ramas, lo que lleva al mejor caso hora. 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 final ordenada, con todos los que lo preceden en un orden no ordenado y todos los que lo siguen en un orden no ordenado. Por lo tanto, una sola llamada recursiva ubica el elemento deseado en la partición correcta, y construimos sobre esto para una selección rápida:
// Devuelve el k-ésimo elemento más pequeño de la lista dentro de left..right inclusive // (es decir, left <= k <= right). function select (list, left, right, k) es si left = right entonces // Si la lista contiene solo un elemento, devuelve list [left] // devuelve ese elemento pivotIndex: = ... // selecciona un pivotIndex entre left y derecha, // por ejemplo, izquierda + piso (rand ()% (derecha - izquierda + 1)) pivotIndex: = partición (lista, izquierda, derecha, pivotIndex) // El pivote está en su posición final ordenada si k = pivotIndex luego devuelve list [k] else if kluego devuelve select (list, left, pivotIndex - 1, k) else return select (list, pivotIndex + 1, right , k)
Tenga en cuenta el parecido con el ordenamiento rápido: así como el algoritmo de selección basado en mínimos es un ordenamiento de selección parcial, este es un ordenamiento rápido parcial, generando y particionando únicamente de su particiones. Este sencillo procedimiento tiene un rendimiento lineal esperado y, al igual que el ordenamiento rápido, 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 la optimización de la llamada de cola está disponible o si se elimina la recursividad de la cola con un bucle:
selección de función (lista, izquierda, derecha, k) es un bucle si izquierda = derecha, luego regresa la lista [izquierda] pivotIndex: = ... // seleccione pivotIndex entre izquierda y derecha pivotIndex: = partición (lista, izquierda, derecha, pivotIndex) if k = pivotIndex entonces devuelve list [k] else if kentonces derecha: = pivotIndex - 1 demás izquierda: = pivotIndex + 1
Complejidad del tiempo
Al igual que la ordenación rápida, la selección rápida tiene un buen rendimiento promedio, pero es sensible al pivote elegido. Si se eligen buenos pivotes, es decir, aquellos que constantemente disminuyen el conjunto de búsqueda en una fracción dada, entonces el conjunto de búsqueda disminuye de 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 la rapidez con que se reduzca el conjunto de búsqueda). Sin embargo, si se eligen constantemente pivotes incorrectos, como la disminución de un solo elemento cada vez, el rendimiento en el peor de los casos es cuadrático:. Esto ocurre, por ejemplo, al buscar el elemento máximo de un conjunto, usar el primer elemento como pivote y tener datos ordenados.
Variantes
La solución más sencilla es elegir un pivote aleatorio, que produce un tiempo lineal casi seguro . De manera determinista, se puede usar la estrategia de pivote de mediana de 3 (como en el ordenamiento rápido), que produce un rendimiento lineal en datos parcialmente ordenados, como es común en el mundo real. Sin embargo, las secuencias artificiales aún pueden causar la complejidad del peor de los casos; David Musser describe una secuencia "asesina mediana de 3" que permite un ataque contra esa estrategia, que fue una de las motivaciones de 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 la mediana de las medianas . Sin embargo, la sobrecarga de calcular el pivote es alta y, por lo tanto, generalmente no se usa en la práctica. Se puede combinar la selección rápida básica con la mediana de las medianas como alternativa para obtener un rendimiento de caso promedio rápido y un rendimiento lineal en el peor de los casos; esto se hace en introselect .
Cálculos más precisos de la complejidad del tiempo promedio producen el peor de los casos de para pivotes aleatorios (en el caso de la mediana; otros k son más rápidos). [2] 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 depara la mediana, mientras que otros k son más rápidos.
Ver también
Referencias
- ^ Hoare, COCHE (1961). "Algoritmo 65: Encontrar". Comm. ACM . 4 (7): 321–322. doi : 10.1145 / 366622.366647 .
- ^ Análisis de Quickselect al estilo Blum , David Eppstein , 9 de octubre de 2007.
enlaces externos
- " qselect ", algoritmo de selección rápida en Matlab, Manolis Lourakis