Introsort o clasificación introspectiva es un algoritmo de clasificación propuesto por David Musseren 1997. Utiliza ordenación rápida y cambia a ordenación heap cuando la profundidad de recurrencia supera un nivel predeterminado (como el logaritmo del número de elementos ordenados). Este enfoque combina las fortalezas de ambos métodos con un O ( n log n ) peor de los casos y una velocidad comparable a la ordenación rápida. Dado que ambos algoritmos utilizan comparaciones, este algoritmo también pertenece a la clase de clasificación basada en comparaciones .
En quicksort, una de las operaciones críticas es la elección de un soporte (el elemento con respecto al cual se divide la matriz). El algoritmo más simple para elegir una base: tomar el primer o último elemento de una matriz como soporte está plagado de mal comportamiento en datos ordenados o casi ordenados. Niklaus Wirth sugirió usar el elemento intermedio para evitar que este caso se degrade a O( n² ) en entradas incorrectas. El algoritmo de selección de la mediana de tres soportes elige la mitad del primer, medio y último elemento de la matriz como soporte. Sin embargo, aunque funciona bien en la mayoría de las entradas, todavía es posible encontrar entradas que ralentizan mucho este algoritmo de clasificación. Dichos datos pueden ser potencialmente utilizados por atacantes. Por ejemplo, los atacantes pueden enviar una matriz de este tipo a un servidor web para lograr una denegación de servicio .
Musser descubrió que en el peor conjunto de datos para la mediana de tres algoritmos de clasificación rápida (se consideró una matriz de 100 000 elementos), la clasificación intro es unas 200 veces más rápida. También evaluó el efecto de caché en el caso de la ordenación de Robert Sedgwick , donde los rangos pequeños se ordenan al final mediante una única pasada de ordenación por inserción . Encontró que este enfoque puede duplicar la cantidad de errores de caché, pero su rendimiento es mucho mejor cuando se usa una deque y debe dejarse para las bibliotecas de plantillas, en parte porque las ganancias no son grandes de otra manera.
La implementación de SGI de la biblioteca de plantillas estándar de C++ ( stl_algo.h ) utiliza el enfoque de control de profundidad de recursión de Musser para la clasificación inestable , cambia a heapsort , elige un elemento fijo como la mediana de tres y finalmente aplica el algoritmo de clasificación por inserción de Knuth para secuencias que contienen menos de 16 elementos.
| Algoritmos de clasificación | |
|---|---|
| Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
| Intercambio | |
| Elección | |
| inserciones | |
| fusión | |
| sin comparaciones | |
| híbrido | |
| Otro | |
| poco práctico | |