En informática , introselect (abreviatura de "selección introspectiva") es un algoritmo de selección que es un híbrido de quickselect 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 ordenamiento introsort : estos son refinamientos análogos de los algoritmos básicos quickselect y quicksort , en el sentido de que ambos comienzan con el algoritmo quick, que tiene un buen rendimiento promedio y una sobrecarga baja, pero retroceden a un algoritmo óptimo en el peor de los casos (con una sobrecarga mayor) si el algoritmo quick no progresa 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, lo que permite 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 quickselect y heapselect , y tiene un tiempo de ejecución en el peor de los casos de O ( n log n ). [2] El borrador del estándar de 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 a quicksort mientras conserva el comportamiento del peor caso O ( n log n ) al crear un híbrido de quicksort y heapsort . 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 caso) si quicksort no avanza lo suficientemente rápido. De manera similar, introselect combina quickselect con median of medians para lograr una selección lineal en el peor caso con un rendimiento similar a quickselect.
Introselect funciona comenzando de manera optimista con una 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 contenido técnico principal del algoritmo. Simplemente limitar la recursión a una profundidad constante no es suficiente, ya que esto haría que el algoritmo cambiara en todas las listas lo suficientemente grandes. Musser analiza un par de enfoques simples:
Ambos enfoques limitan la profundidad de recursión 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 introselección, pero el autor se retiró en 2007 sin haber publicado ninguna investigación adicional al respecto.