¿Qué algoritmo utilizan los compiladores de C ++ populares para std :: sort y std :: stable_sort?

Acabo de echar un vistazo a los encabezados C ++ instalados en mi sistema por g ++ – 4.5 para confirmar mi sospecha de que g ++ usa Introsort , que combina el ordenamiento rápido , el ordenamiento dinámico y el tipo de inserción.

Para listas grandes (más de 16 elementos), esta versión de std :: sort usa quicksort con una partición mediana de tres; debajo del límite de 16 elementos, en su lugar se utiliza la ordenación por inserción. Sin embargo, si la profundidad de recursión debe ser demasiado alta debido a una partición desequilibrada (más del doble del registro binario del tamaño de la lista), entonces cambia a ordenamiento dinámico.

De esta manera, la mayoría de las listas se pueden ordenar muy rápidamente porque el ordenamiento rápido generalmente tiene el factor constante más bajo de todos los algoritmos O (n log n). La partición mediana de tres asegura que las listas ordenadas, casi ordenadas y ordenadas al revés no causarán particiones desiguales. Sin embargo, incluso en el caso de una confrontación de entrada para la partición de la mediana de tres, el peor caso de O (n ^ 2) se evita mediante el retroceso al montón.

std :: stable_sort usa mergesort.

C ++ sort () usa Introsort y Insertion sort. La clasificación de introducción en sí es una combinación de clasificación rápida y de montón. [1]

Como sabemos debido al pequeño factor constante en la ordenación por inserción en comparación con la ordenación rápida y el almacenamiento dinámico, la ordenación por inserción es más rápida cuando el número de elementos es menor y está en forma casi ordenada . Por lo tanto, usar esta heurística sería beneficioso en mi opinión.

Referencia:
http://en.wikipedia.org/wiki/Sor …

Hay dos algoritmos que se usan tradicionalmente.

Es muy probable que std::sort use QuickSort, o al menos una variación sobre QuickSort llamada IntroSort, que “degenera” en HeapSort cuando la recursión es demasiado profunda.

De la norma:

Complejidad: comparaciones O (N log (N)).

Es muy probable que std::stable_sort use MergeSort, debido al requisito de estabilidad. Sin embargo, tenga en cuenta que MergeSort requiere espacio adicional para ser eficiente.

De la norma:

Complejidad: lo hace a lo sumo N log

2

(N) comparaciones; si hay suficiente memoria adicional disponible, es N log (N).

Creo que estos se usan en los compiladores modernos de lenguaje C.

Espero eso ayude

Gracias

std :: sort es “casi obligatorio” para ser introsort, porque los requisitos de complejidad actuales son O (n log n) caso promedio y O (n log n) peor caso. (Solía ​​ser el peor de los casos O (n ^ 2), antes de que existiera el introsort, porque se esperaba una implementación rápida de calidad).

std :: stable_sort siempre es mergesort, y se puede ver en los requisitos de complejidad -> O (n log n) si la implementación puede asignar memoria adicional, O (n log (n) log (n)) si no puede.

Para detalles adicionales sobre esto, lea la respuesta de Brian Bi, no hay mucho más que decir. (Bueno, excepto que las constantes y el tamaño medio (no una palabra real) difieren según la implementación y soy mucho más parcial con respecto a la implementación de STL de MS en lo que respecta a los tipos)

Pero hay otro algoritmo de ordenación sobre el que no preguntó, y es std :: partial_sort. Se implementa mediante ordenamiento dinámico, específicamente crea un montón máximo de todos los elementos y luego lo ajusta hasta que solo contiene elementos [primero, medio], que luego clasifica.