Introsort - Introsort

Introsort

Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	O ( n log n )
Rendimiento medio	O ( n log n )

Introsort o ordenación introspectiva es un algoritmo de ordenación híbrido que proporciona tanto un rendimiento medio rápido como un rendimiento óptimo (asintóticamente) en el peor de los casos. Comienza con ordenación rápida , cambia a ordenación por pila cuando la profundidad de recursividad excede un nivel basado en (el logaritmo de) la cantidad de elementos que se ordenan y cambia a ordenación por inserción cuando la cantidad de elementos está por debajo de algún umbral. Esto combina las partes buenas de los tres algoritmos, con un rendimiento práctico comparable al de clasificación rápida en conjuntos de datos típicos y en el peor de los casos O ( n log n) tiempo de ejecución debido al tipo de pila. Dado que los tres algoritmos que utiliza son tipos de comparación , también es un tipo de 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 se reduce a la mediana de las medianas y, por lo tanto, proporciona una complejidad lineal en el peor de los casos, que es óptimo. Ambos algoritmos se introdujeron con el propósito de proporcionar algoritmos genéricos para la biblioteca estándar de C ++ que tenían un rendimiento promedio rápido y un rendimiento óptimo en el peor de los casos, lo que permitía ajustar los requisitos de rendimiento. Introsort está en su lugar y no es estable .

Pseudocódigo

Si una implementación de heapsort y funciones de particionamiento del tipo que se describe en el artículo de quicksort están disponibles, el introsort puede describirse sucintamente como

procedure sort(A : array):
    let maxdepth = ⌊log(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[0: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 matriz de elementos i a j .

Análisis

En Quicksort, una de las operaciones críticas es elegir el pivote: el elemento alrededor del cual se particiona 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 provoca un comportamiento deficiente en el caso de una entrada ordenada o casi ordenada. La variante de Niklaus Wirth usa el elemento intermedio para prevenir estas ocurrencias, degenerando en O ( n ² ) 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, todavía es posible idear una lista de asesinos de mediana de 3 que causará una ralentización drástica de una clasificación rápida basada en esta técnica de selección dinámica.

Musser informó que en una secuencia asesina mediana de 3 de 100,000 elementos, el tiempo de ejecución de introsort fue 1/200 del de la clasificación rápida de mediana de 3. Musser también consideró el efecto sobre los cachés de la clasificación pequeña retardada de Sedgewick , donde los rangos pequeños se clasifican al final en una sola pasada de clasificación por inserción . Informó 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 ganancia en otros casos al realizar las clasificaciones de inmediato no fue muy grande.

Implementaciones

Introsort o alguna variante se utiliza en una serie de funciones de ordenación de bibliotecas estándar , incluidas algunas implementaciones de ordenación de C ++ .

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

La biblioteca GNU Standard C ++ es similar: usa introsort con una profundidad máxima de 2 × log ₂ n , seguido de una ordenación por inserción en particiones menores de 16.

La biblioteca de clases de Microsoft .NET Framework , a partir de la versión 4.5 (2012), usa introsort en lugar de una ordenación rápida simple.

Go usa introsort con una pequeña modificación: para cortes de 12 elementos o menos, usa Shellsort en lugar del ordenamiento por inserción , y una mediana más avanzada de tres medianas de la selección de tres pivotes para quicksort.

Variantes

pdqsort

Quicksort que derrota patrones (pdqsort) es una variante de introsort que incorpora las siguientes mejoras:

• Mediana de tres pivotantes,
• Técnica de partición "BlockQuicksort" para mitigar las penalizaciones por predicción errónea de rama,
• Rendimiento de tiempo lineal para ciertos patrones de entrada ( ordenación adaptativa ),
• Utilice la mezcla de elementos en casos defectuosos antes de probar la clasificación de pila más lenta.

Rust y GAP usan pdqsort.

Referencias

General