Quels algorithmes sont utilisés dans C ++11 std :: sort dans différentes implémentations STL?

Question

Le C++11 standard garantit std::sort a O(n logn) de la complexité dans le pire des cas. Ceci est différent de la moyenne des cas de garantie en C++98/03, où std::sort pourraient être mises en œuvre avec Quicksort (peut-être combiné avec le tri par insertion pour les petits n), qui a O(n^2) dans le pire des cas (pour certaines d'entrée spécifiques, telles que l'entrée triée).

Y avait-il des changements en std::sort mises en œuvre dans les différents STL bibliothèques? Comment est le C++11 std::sort mis en œuvre dans différents Lse?

Answer 1

La question est, comment pouvez - STL - dire std::sort pire des cas est O(N log(N)), même si elle est, par essence, un QuickSort. Du TSL, le tri est IntroSort. IntroSort est, par essence, un QuickSort, la différence introduite changer le pire des cas de complexité.

---

QuickSort pire des cas est O(N^2)

Ce que jamais vous choisissez le partitionnement, il existe une séquence de QuickSort sera exécuté sur O(N^2). Le partitionnement vous choisissez seulement diminue la probabilité de le pire des cas de se produire. (Aléatoire Pivot de la Sélection , de la Médiane De Trois, etc.)

EDIT: Merci à @maxim1000 s de correction. Quicksort avec pivot algorithme de sélection de la Médiane des Médianes a O(N log(N)) le pire des cas, la complexité, mais en raison de la surcharge qu'il introduit, il n'est pas utilisé dans la pratique. Il montre comment bon algorithme de sélection, peut changer le pire-la complexité de l'affaire par le biais de pivot de la sélection, en théorie.

---

Ce n'IntroSort faire?

IntroSort les limites de la ramification de QuickSort. C'est le point le plus important, la limite est de 2 * (log N). Lorsque la limite est atteinte, IntroSort pouvez utiliser n'importe quel algorithme de tri qui a le pire des cas, la complexité de O(N log(N)).

La ramification s'arrête lorsque nous avons O(log N) sous-problèmes. Nous pouvons résoudre tous les subproblem O(n log n). (Minuscules n représente le subproblem tailles).

Somme de (n log n) est notre pire la complexité de l'affaire, maintenant.

Pour le pire des cas de QuickSort; supposons que nous disposons déjà d'un tableau trié, et nous choisissons toujours le premier élément de ce tableau que le pivot. Dans chaque itération, nous nous débarrassons de la seulement le premier élément. Si nous continuons de cette façon jusqu'à la fin, il serait O(N^2) évidemment. Avec IntroSort nous arrêter QuickSort, quand nous arrivons à une profondeur log(N), puis nous utilisons HeapSort pour le reste des ménagères de tableau.

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))**/

Les résume;

Jusqu'à ce que la ramification s'arrête, N + (N - 1) + ... + (N - log(N)) les opérations effectuées. Au lieu d'utiliser gauss pour résumer, nous pouvons dire plus simplement N + (N - 1) + ... + (N - log(N)) < N log(N).

Le HeapSort Partie est - (N - log(N)) log(N - log(N)) < N log(N)

La complexité globale < 2 N log(N).

Depuis les constantes peuvent être omis, le pire des cas, la complexité de IntroSort est O(N log(N)).

---

Ajout d'Infos: GCC STL mise en œuvre du code source est ici. Sort de la fonction est à la ligne 5461.

Correction: *Microsoft .NET* trier la mise en Œuvre est IntroSort depuis 2012. L'information correspondante est ici.

Answer 2

La navigation sur les sources en ligne pour libstdc++ et de la libc++, on peut voir que les deux bibliothèques de l'utilisation de toute la gamme de la célèbre algorithmes de tri à partir d'une intro-tri boucle principale:

Pour std::sort, il est d'une aide de la routine insertion_sort (un O(N^2) algorithme, mais avec une bonne mise à l'échelle de la constante pour le rendre compétitif pour les petites séquences), en plus de certains de revêtement spécial pour les sous-séquences de 0, 1, 2, et 3 éléments.

Pour std::partial_sort, les deux bibliothèques de l'utilisation d'une version de l' heap_sort (O(N log N) en général), car cette méthode a une belle invariant qu'elle garde une triés sous-suite (il a généralement une plus grande constante d'échelle pour le rendre plus cher pour plein de tri).

Pour std::nth_element, il est d'une aide de la routine selection_sort (encore une O(N^2) l'algorithme avec une bonne sclaing constante pour le rendre compétitif pour les petites séquences). Régulièrement tri insertion_sort domine, souvent, selection_sort, mais pour l' nth_element l'invariant d'avoir le plus petit des éléments parfaitement le comportement de l' selection_sort.