Introsort u ordenación introspectiva es un algoritmo de ordenación híbrido que proporciona tanto un rendimiento promedio rápido como un rendimiento óptimo (asintóticamente) en el peor de los casos. Comienza con quicksort , cambia a heapsort cuando la profundidad de recursión excede un nivel basado en (el logaritmo de) la cantidad de elementos que se están ordenando y cambia a ordenación por inserción cuando la cantidad de elementos está por debajo de un umbral. Esto combina las partes buenas de los tres algoritmos, con un rendimiento práctico comparable a quicksort en conjuntos de datos típicos y un tiempo de ejecución O ( n log n ) en el peor de los casos debido a la ordenación por heap. 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 las 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 permitiera ajustar los requisitos de rendimiento. [1] Introsort es un algoritmo in situ y no estable .
Si están disponibles una implementación de heapsort y funciones de partición del tipo discutido en el artículo de ordenación rápida , la introordenación 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: ordenación por montículos (A) demás : p ← partición(A) // supongamos que esta función realiza la selección del pivote, p es la posición final del pivote introsort(A[1:p-1], profundidad máxima - 1) introsort(A[p+1:n], profundidad máxima - 1)
El factor 2 en la profundidad máxima es arbitrario; se puede ajustar para obtener 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 quicksort, una de las operaciones críticas es elegir el pivote: el elemento alrededor del cual se divide la lista. El algoritmo de selección de pivote más simple es tomar el primer o el último elemento de la lista como pivote, lo que causa un comportamiento deficiente para el caso de una entrada ordenada o casi ordenada. La variante de Niklaus Wirth usa el elemento del medio para evitar estas ocurrencias, degenerando a O( n 2 ) para secuencias artificiales. El algoritmo de selección de pivote de mediana de 3 toma la mediana del primer, medio y último elemento de la lista; sin embargo, aunque esto funciona bien en muchas entradas del mundo real, aún es posible idear una lista asesina de mediana de 3 que causará una desaceleración dramática de un quicksort basado en esta técnica de selección de pivote.
Musser informó que en una secuencia asesina de 100.000 elementos con una mediana de 3, el tiempo de ejecución de introsort fue 1/200 del de quicksort con una mediana de 3. Musser también consideró el efecto en los cachés de la ordenación pequeña retrasada de Sedgewick , donde los rangos pequeños se ordenan al final en una sola pasada de ordenación por inserción . Informó que podría duplicar la cantidad de errores 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 ganancia en otros casos de hacer las ordenaciones inmediatamente no era grande.
Introsort o alguna variante se utiliza en varias funciones de ordenamiento de la biblioteca estándar , incluidas algunas implementaciones de ordenamiento de C++ .
La implementación stl_algo.h de la biblioteca de plantillas estándar C++ SGI de junio de 2000 de la ordenación inestable utiliza el enfoque de introordenación de Musser con la profundidad de recursión para cambiar a la ordenación por montículo pasada como parámetro, la selección de pivote de mediana de 3 y el pase de ordenación por inserción final de Knuth para particiones más pequeñas que 16.
La biblioteca C++ estándar de GNU es similar: utiliza una ordenación por inserción con una profundidad máxima de 2×log 2 n , seguida de una ordenación por inserción en particiones menores a 16. [2]
LLVM libc++ también utiliza introsort con una profundidad máxima de 2×log 2 n , sin embargo, el límite de tamaño para la ordenación por inserción es diferente para los distintos tipos de datos (30 si los intercambios son triviales, 6 en caso contrario). Además, las matrices 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 Microsoft .NET Framework , a partir de la versión 4.5 (2012), utiliza introsort en lugar de quicksort simple. [5]
Go utiliza una modificación de introsort: para porciones de 12 elementos o menos, utiliza la ordenación por inserción , y para porciones más grandes, utiliza la ordenación rápida que anula patrones y una mediana más avanzada de tres medianas para la selección de pivotes. [6] Antes de la versión 1.19, utilizaba la ordenación de shell para porciones pequeñas.
Java , a partir de la versión 14 (2020), utiliza un algoritmo de ordenamiento híbrido que utiliza la ordenación por fusión para matrices altamente estructuradas (matrices que se componen de una pequeña cantidad de submatrices ordenadas) y la ordenación por introspección para ordenar matrices de ints, longs, floats y doubles. [7]
La clasificación rápida que derrota patrones (pdqsort) es una variante de la clasificación introspectiva que incorpora las siguientes mejoras: [8]
pdqsort es utilizado por Rust , GAP , [9] y la biblioteca C++ Boost . [10]
fluxsort es una variante estable de introsort que incorpora las siguientes mejoras: [11]
Las mejoras introducidas por fluxsort y su variante inestable, crumsort, fueron adoptadas por crumsort-rs, glidesort, ipnsort y driftsort. El aumento general del rendimiento en entradas aleatorias en comparación con pdqsort es de alrededor del 50 %. [12] [13] [14] [15] [16]
El algoritmo actual se basa en el quicksort que anula patrones de Orson Peters, que combina el caso promedio rápido del quicksort aleatorio con el peor caso rápido del heapsort, al tiempo que logra un tiempo lineal en porciones con ciertos patrones. Utiliza cierta aleatorización para evitar casos degenerados, pero con una semilla fija para proporcionar siempre un comportamiento determinista.