libreria - sort vector c++

¿Qué algoritmos se utilizan en C++ 11 std:: sort en diferentes implementaciones de STL?

Question

El estándar C ++ 11 garantiza que std::sort tiene complejidad O (n logn) en el peor de los casos . Esto es diferente de la garantía de caso promedio en C ++ 98/03, donde std::sort podría implementarse con Quicksort (quizás combinado con ordenar por inserción para n pequeña), que tiene O (n ^ 2) en el peor de los casos (para alguna entrada específica, como entrada ordenada).

¿Hubo algún cambio en las implementaciones std::sort en diferentes bibliotecas STL? ¿Cómo se implementa el std::sort C ++ 11 en diferentes STL?

Answer 1

Al navegar por las fuentes en línea para libstdc++ y libc++ , se puede ver que ambas bibliotecas usan la gama completa de algoritmos de clasificación bien conocidos de un bucle principal de clasificación intro:

Para std::sort , hay una rutina auxiliar para insertion_sort (un algoritmo O(N^2) pero con una buena constante de escala para hacerlo competitivo para secuencias pequeñas), más alguna carcasa especial para subsecuencias de 0, 1, 2 y 3 elementos.

Para std::partial_sort , ambas bibliotecas usan una versión de heap_sort ( O(N log N) en general), porque ese método tiene una buena invariante que mantiene una subsecuencia ordenada (generalmente tiene una constante de escalado mayor para encarecerla). para una clasificación completa).

Para std::nth_element , hay una rutina de ayuda para selection_sort (de nuevo un algoritmo O (N ^ 2) con una buena constante de sclaing para hacerlo competitivo para secuencias pequeñas). Para la clasificación regular, insertion_sort generalmente domina selection_sort , pero para nth_element la invariante de tener los elementos más pequeños se nth_element perfectamente al comportamiento de selection_sort .

Answer 2

La pregunta es, ¿cómo puede STL decir que std::sort peor de los casos es O (N log (N)) , a pesar de que en esencia es una QuickSort . El tipo de STL es IntroSort . IntroSort es, en esencia, una QuickSort, la diferencia introducida cambia la peor de las situaciones.

El peor caso de QuickSort es O (N ^ 2)

Cualquiera que sea el particionamiento que elija, existe una secuencia que QuickSort ejecutará en O (N ^ 2) . La partición que elija solo disminuye la probabilidad de que ocurra el peor de los casos. ( Selección aleatoria de pivote , Mediana-de-tres, etc. )

EDITAR: Gracias a la corrección de @ maxim1000 s. Quicksort con algoritmo de selección de pivote Median of Medians tiene O (N log (N)) complejidad del peor caso, pero debido a la sobrecarga que introduce, no se utiliza en la práctica. Muestra cómo un buen algoritmo de selección puede cambiar la complejidad del caso más desfavorable a través de la selección dinámica, teóricamente.

¿Qué hace IntroSort?

IntroSort limita la ramificación de QuickSort. Este es el punto más importante, ese límite es 2 * (log N) . Cuando se alcanza el límite, IntroSort puede usar cualquier algoritmo de clasificación que tenga la peor complejidad de caso de O (N log (N)).

La ramificación se detiene cuando tenemos subproblemas O (log N). Podemos resolver cada subproblema O (n log n). (Minúscula n representa el tamaño del subproblema).

La suma de (n log n) es nuestra peor complejidad de caso, ahora.

Para el peor caso de QuickSort; supongamos que tenemos una matriz ya ordenada, y seleccionamos siempre el primer elemento en esta matriz como pivote. En cada iteración, nos deshacemos del primer elemento. Si vamos por este camino hasta el final, sería O (N ^ 2) obviamente. Con IntroSort detenemos QuickSort, cuando alcanzamos un registro de profundidad (N) , entonces usamos HeapSort para la matriz no ordenada restante.

16 -> 1  /**N**/
   /
    > 15 -> 1 /**N - 1**/
         /
          > 14 -> 1 /**N - 2**/
               /
                > 13 -> 1 /**N - log(N)**/  
                     /
                      > 12 /**(HeapSort Now) (N - log(N)) log (N - log(N))**/

Resúmalos;

Hasta que se detenga la bifurcación, se realizan las operaciones N + (N - 1) + ... + (N - log(N)) . En lugar de usar gauss para resumir, simplemente podemos decir N + (N - 1) + ... + (N - log(N)) < N log(N) .

La parte HeapSort es (N - log(N)) log(N - log(N)) < N log(N)

Complejidad general < 2 N log(N) .

Como las constantes se pueden omitir, la peor complejidad de IntroSort es O (N log (N)) .

Información agregada: el código fuente de implementación de GCC STL está here . Sort función de ordenación está en la línea 5461 .

Corrección: * La implementación de Microsoft .NET * sort es IntroSort desde 2012. La información relacionada está here .