En informática , introselect (abreviatura de "selección introspectiva") es un algoritmo de selección que es un híbrido de selección rápida y mediana de medianas que tiene un rendimiento promedio rápido y un rendimiento óptimo en el peor de los casos. Introselect está relacionado con el algoritmo de ordenación introsort : estos son refinamientos análogos de los algoritmos básicos de selección rápida y ordenación rápida , en el sentido de que ambos comienzan con el algoritmo rápido, que tiene un buen rendimiento promedio y una sobrecarga baja, pero recurren a un algoritmo óptimo en el peor de los casos. (con mayor sobrecarga) si el algoritmo rápido no avanza lo suficientemente rápido. Ambos algoritmos fueron introducidos por David Musser en (Musser 1997), con el propósito de proporcionar algoritmos genéricos para la biblioteca estándar de C++ que tengan un rendimiento promedio rápido y un rendimiento óptimo en el peor de los casos, permitiendo así ajustar los requisitos de rendimiento. [1]
Sin embargo, en la mayoría de las implementaciones de la biblioteca estándar de C++, se utiliza un algoritmo de "introselección" diferente, que combina selección rápida y selección de montón , y tiene un tiempo de ejecución en el peor de los casos de O ( n log n ). [2] El borrador del estándar C++, a partir de 2022, no tiene requisitos sobre el rendimiento en el peor de los casos, por lo que permite dicha elección. [3]
Introsort logra un rendimiento práctico comparable al de clasificación rápida al tiempo que preserva el peor comportamiento O ( n log n ) al crear un híbrido de clasificación rápida y clasificación en montón . Introsort comienza con Quicksort, por lo que logra un rendimiento similar a Quicksort si Quicksort funciona, y vuelve a Heapsort (que tiene un rendimiento óptimo en el peor de los casos) si Quicksort no progresa lo suficientemente rápido. De manera similar, la introselección combina la selección rápida con la mediana de medianas para lograr la selección lineal en el peor de los casos con un rendimiento similar a la selección rápida.
Introselect funciona comenzando de manera optimista con la selección rápida y solo cambiando a un algoritmo de selección de tiempo lineal en el peor de los casos (el algoritmo de mediana de medianas de Blum-Floyd-Pratt-Rivest-Tarjan ) si se repite demasiadas veces sin lograr un progreso suficiente. La estrategia de cambio es el principal contenido técnico del algoritmo. Simplemente limitar la recursividad a una profundidad constante no es suficiente, ya que esto haría que el algoritmo active todas las listas suficientemente grandes. Musser analiza un par de enfoques simples:
Ambos enfoques limitan la profundidad de recursividad a k ⌈log n ⌉ = O (log n ) y el tiempo total de ejecución a O ( n) .
El artículo sugería que se realizarían más investigaciones sobre la introselecta, pero el autor se retiró en 2007 sin haber publicado ninguna investigación adicional.