Selección de introducción

En informática , introselect (abreviatura de "selección introspectiva") es un algoritmo de selección híbrido de quickselect y mediana de medianas que ofrece 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 : ambos son refinamientos análogos de los algoritmos básicos quickselect y quicksort , ya que ambos parten del algoritmo quick, que ofrece un buen rendimiento promedio y una baja sobrecarga, pero recurren a un algoritmo óptimo en el peor de los casos (con mayor sobrecarga) si el algoritmo quick no avanza con la suficiente rapidez. 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 ofrecieran tanto un rendimiento promedio rápido como un rendimiento óptimo en el peor de los casos, lo que permitía 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 "introselect" 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 al de quicksort, manteniendo un comportamiento en el peor de los casos de O ( n log n ) mediante la creación de un híbrido entre quicksort y heapsort . Introsort comienza con quicksort, por lo que alcanza un rendimiento similar si quicksort funciona, y recurre a heapsort (que ofrece un rendimiento óptimo en el peor de los casos) si quicksort no avanza con la suficiente rapidez. De manera similar, introselect combina quickselect con la mediana de medianas para lograr una selección lineal en el peor de los casos con un rendimiento similar al de quickselect.

Introselect funciona comenzando de forma optimista con quickselect y 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 recurre demasiadas veces sin lograr un progreso suficiente. La estrategia de cambio es el contenido técnico principal del algoritmo. Limitar la recursión a una profundidad constante no es suficiente, ya que esto haría que el algoritmo cambiara en todas las listas suficientemente grandes. Musser analiza un par de enfoques sencillos:

• Mantén un registro de la lista de tamaños de las subparticiones procesadas hasta el momento. Si en algún momento se han realizado k llamadas recursivas sin reducir a la mitad el tamaño de la lista, para algún valor positivo pequeño de k , cambia al algoritmo lineal del peor caso.
• Suma el tamaño de todas las particiones generadas hasta el momento. Si este resultado supera el tamaño de la lista multiplicado por una pequeña constante positiva k , cambia al algoritmo lineal del peor caso. Esta suma se puede llevar fácilmente en una sola variable escalar.

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 introselectividad, pero el autor se jubiló en 2007 sin haber publicado ninguna investigación adicional al respecto.

• Algoritmo de Floyd-Rivest