Introsort

Introsort o ordenación introspectiva es un algoritmo de ordenación híbrido que proporciona un rendimiento promedio rápido y un rendimiento óptimo (asintóticamente) en el peor de los casos. Comienza con quicksort , cambia a heapsort cuando la profundidad de recursión supera un nivel basado en (el logaritmo de) el número de elementos que se están ordenando y cambia a ordenación por inserción cuando el número de elementos está por debajo de un cierto umbral. Esto combina las mejores partes de los tres algoritmos, con un rendimiento práctico comparable a quicksort en conjuntos de datos típicos y un tiempo de ejecución en el peor de los casos de O ( n log n ) gracias a la ordenación por montículo. Dado que los tres algoritmos que utiliza son ordenaciones por comparación , también es una ordenación por comparación.

Introsort fue inventado por David Musser en Musser (1997) , en el que también introdujo introselect , un algoritmo de selección híbrido basado en quickselect (una variante de quicksort), que recurre a la mediana de medianas y, por lo tanto, proporciona una complejidad lineal en el peor de los casos, que es óptima. Ambos algoritmos se introdujeron con el propósito de proporcionar algoritmos genéricos para la biblioteca estándar de C++ que tuvieran un rendimiento promedio rápido y un rendimiento óptimo en el peor de los casos, lo que permitió ajustar los requisitos de rendimiento. ^{[ 1 ]} Introsort es un algoritmo in situ y no estable .

Si se dispone de una implementación de heapsort y funciones de particionamiento del tipo analizado en el artículo sobre quicksort , el introsort se puede describir sucintamente como

procedimiento sort(A : array): profundidad máxima ← ⌊log 2 (longitud(A))⌋ × 2 introsort(A, profundidad máxima) procedimiento introsort(A, maxdepth): n ← longitud(A) Si n < 16: ordenación por inserción(A) de lo contrario, si maxdepth = 0: ordenamiento por montículo(A) demás : p ← partición(A) // Supongamos que esta función realiza una selección de pivote, p es la posición final del pivote. introsort(A[1:p-1], maxdepth - 1) introsort(A[p+1:n], maxdepth - 1)

El factor 2 en la profundidad máxima es arbitrario; se puede ajustar para un rendimiento práctico. A [ i : j ] denota la porción de la matriz de elementos i a j que incluye tanto A [ i ] como A [ j ] . Se supone que los índices comienzan con 1 (el primer elemento de la matriz A es A[1] ).

En el algoritmo Quicksort, una de las operaciones críticas es la elección del pivote: el elemento alrededor del cual se divide la lista. El algoritmo de selección de pivote más simple consiste en tomar el primer o el último elemento de la lista como pivote, lo que provoca un comportamiento deficiente en el caso de entradas ordenadas o casi ordenadas. La variante de Niklaus Wirth utiliza el elemento central para evitar estas situaciones, degenerando a O( n² ) para secuencias artificiales. El algoritmo de selección de pivote mediana de ³ toma la mediana del primer, el elemento central y el último elemento de la lista; sin embargo, aunque funciona bien con muchas entradas reales, aún es posible crear una lista de pivote mediana de 3 que cause una ralentización drástica en un Quicksort basado en esta técnica de selección de pivote.

Musser informó que, en una secuencia de 100 000 elementos con mediana de 3, el tiempo de ejecución de introsort era 1/200 del de quicksort con mediana de 3. Musser también consideró el efecto en las cachés de la ordenación pequeña retardada de Sedgewick , donde los rangos pequeños se ordenan al final en una sola pasada de ordenación por inserción . Indicó que podría duplicar el número de fallos de caché, pero que su rendimiento con colas de doble extremo era significativamente mejor y debería conservarse para las bibliotecas de plantillas, en parte porque la mejora en otros casos al realizar las ordenaciones inmediatamente no era grande.

Introsort, o alguna de sus variantes, se utiliza en varias funciones de ordenación de la biblioteca estándar , incluidas algunas implementaciones de ordenación de C++ .

La implementación stl_algo.h de la biblioteca de plantillas estándar de C++ de SGI de junio de 2000 para la ordenación inestable utiliza el enfoque de introsort de Musser con la profundidad de recursión para cambiar a heapsort pasada como parámetro, selección de pivote mediana de 3 y la pasada de ordenación de inserción final de Knuth para particiones menores de 16.

La biblioteca estándar de C++ de GNU es similar: utiliza introsort con una profundidad máxima de 2×log ₂ n , seguida de una ordenación por inserción en particiones menores de 16. ^{[ 2 ]}

LLVM libc++ también utiliza introsort con una profundidad máxima de 2×log ₂ n , sin embargo, el límite de tamaño para la ordenación por inserción es diferente para distintos tipos de datos (30 si los intercambios son triviales, 6 en caso contrario). Además, los arreglos con tamaños de hasta 5 se manejan por separado. ^{[ 3 ]} Kutenin (2022) proporciona una descripción general de algunos cambios realizados por LLVM, con un enfoque en la corrección de 2022 para la cuadraticidad. ^{[ 4 ]}

La biblioteca de clases de Microsoft .NET Framework , a partir de la versión 4.5 (2012), utiliza introsort en lugar del simple quicksort. ^{[ 5 ]}

Go utiliza una modificación de introsort: para segmentos de 12 elementos o menos utiliza el ordenamiento por inserción , y para segmentos más grandes utiliza quicksort que evita patrones y una mediana más avanzada de tres medianas para la selección del pivote. ^{[ 6 ]} Antes de la versión 1.19 utilizaba shell sort para segmentos pequeños.

Java , a partir de la versión 14 (2020), utiliza un algoritmo de ordenación híbrido que emplea la ordenación por fusión para matrices altamente estructuradas (matrices compuestas por un pequeño número de submatrices ordenadas) y la ordenación introspectiva en los demás casos para ordenar matrices de enteros, números largos, números de coma flotante y números de coma flotante. ^{[ 7 ]}