c++ - libreria - ¿Qué tipo de clasificación se usa en std:: sort()?
sort string c++ (6)
¿Te refieres a std :: sort? De ser así, puede implementarse de la forma que quiera. Probablemente sea de tipo Quick pero podría ser raíz o algo más. Siempre y cuando le produzca una lista ordenada en al menos O (n log n), la implementación está bien, afaik.
¿Puede alguien decirme qué tipo de técnica de ordenación (burbuja, inserción, selección, rápida, fusión, conteo ...) se implementa en la función std::sort() definida en el archivo de encabezado <algorithm> ?
Hay tres algoritmos que se usan en MSVC2013 STL, que hacen referencia al código fuente de std::sort .
Es más probable que use
QuickSort, o una variación sobreQuickSortllamadaIntroSort.Si la recursión es demasiado profunda,
HeapSortse usará aquí.De
InsertSortcontrario, se usaráInsertSort.
La mayoría de las implementaciones de std::sort usan quicksort, (o generalmente un algoritmo híbrido como introsort, que combina quicksort, heapsort e insert sort).
Lo único que requiere el estándar es que std::sort clasifique de alguna manera los datos de acuerdo con el orden especificado con una complejidad de aproximadamente O (N log (N)); no se garantiza que sea estable. Técnicamente, introsort cumple mejor con los requisitos de complejidad que con el servicio de envío rápido, ya que el servicio de envío rápido tiene un tiempo cuadrático del peor de los casos.
Norma C ++ ISO / IEC 14882: 2003
25.3.1.1 clasificación
template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);1 Efectos : ordena los elementos en el rango [primero, último).
2 Complejidad : Aproximadamente N log N (donde N == último - primero) comparaciones en promedio.
No hay información sobre el método, pero la complejidad siempre es N log N
Probablemente todas las implementaciones de std::sort usan introsort (también conocido como introspection sort ), un algoritmo híbrido que combina quicksort y heapsort. En realidad, el introsort fue inventado en particular en 1997 con el propósito de una implementación de clasificación de rendimiento en C ++ STL.
Lo único que requiere el estándar es que std::sort clasifique de alguna manera los datos de acuerdo con el orden especificado con una complejidad de O (N log (N)) ; no se garantiza que sea estable (hay un algoritmo separado std::stable_sort disponible, si esto fuera necesario).
Técnicamente, introsort cumple mejor con los requisitos de complejidad que el quicksort: esto se debe a que heapsort tiene una complejidad O (N log (N)) garantizada en el peor de los casos, mientras que el quicksort tiene un tiempo cuadrático del peor de los casos.
Sin embargo, heapsort es ''más lento'' que quicksort en el caso promedio, en el sentido de que heapsort realiza C * N log (N) mientras que quicksort tiene D * N log (n) rendimiento, siendo D significativamente menor que C (los números C y D son constantes). En otras palabras, la sobrecarga por comparación del heapsort es más alta que la de quicksort.
Para obtener lo mejor de ambos mundos, introsort comienza con quicksort, un algoritmo recursivo, pero cuando la profundidad de recursión es demasiado alta (lo que significa que entra en un peor comportamiento degenerado ), cambia a heapsort.
Consulte también la entrada de Wikipedia para introsort o el documento original de David Musser, quien inventó introsort particularmente para STL.
Solo algunos resultados empíricos:
Traduje un script de Python usando Numpy 1.9.2 sort a C ++ usando std :: sort (VS2008 toolchain).
Solo obtengo los mismos resultados exactos en Python y C ++ cuando uso el argumento numpy.sort kind = ''mergesort''. Obtengo ordenamiento relativo diferente para elementos con la misma clave cuando kind = ''quicksort'' o kind = ''heapsort''. Así que supongo que al menos para la versión de STL que viene con VS2008 std :: sort usa mergesort.