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

Le standard C ++ 11 garantit que std::sort a la complexité O (n logn) dans le pire des cas . Ceci est différent de la garantie moyenne en C ++ 98/03, où std::sort pourrait être implémenté avec Quicksort (peut-être combiné avec un sorting par insertion pour n), qui a O (n ^ 2) dans le pire des cas (pour certaines entrées spécifiques, telles que les entrées sortingées).

Y at-il eu des changements dans les implémentations std::sort dans différentes bibliothèques STL? Comment std::sort C ++ 11 est-il implémenté dans différentes STL?

En parcourant les sources en ligne pour libstdc ++ et libc ++ , on peut voir que les deux bibliothèques utilisent toute la gamme des algorithmes de sorting bien connus d’une boucle principale d’intro-sorting:

Pour std::sort , il existe une routine auxiliaire pour insertion_sort (un algorithme O(N^2) mais avec une constante de mise à l’échelle pour le rendre compétitif pour les petites séquences), ainsi que des boîtiers spéciaux pour les sous-séquences de 0, 1, 2 et 3 éléments.

Pour std::partial_sort , les deux bibliothèques utilisent une version de heap_sort ( O(N log N) en général), car cette méthode a un bon invariant qu’elle conserve une sous-séquence sortingée (elle a généralement une constante de mise à l’échelle plus élevée pour la rendre plus chère) pour un sorting complet).

Pour std::nth_element , il existe une routine d’assistance pour selection_sort (encore un algorithme O (N ^ 2) avec une bonne constante de sclaing pour le rendre compétitif pour les petites séquences). Pour un sorting régulier, nth_element domine généralement selection_sort , mais pour nth_element l’invariant d’avoir les plus petits éléments correspond parfaitement au comportement de selection_sort .

La question est la suivante: comment STL peut-il dire std::sort pire des cas est O (N log (N)) , même s’il est essentiellement un QuickSort . Le sorting de STL est IntroSort . IntroSort est essentiellement un QuickSort, la différence introduite modifie la complexité du cas le plus défavorable.


Le pire cas de QuickSort est O (N ^ 2)

Quelle que soit la partition que vous choisissez, il existe une séquence que QuickSort exécutera sur O (N ^ 2) . Le partitionnement que vous choisissez ne diminue que la probabilité que le pire cas se produise. ( Sélection de pivot aléatoire , médiane de trois, etc. )

EDIT: Merci à @ maxim1000 s correction. Quicksort avec algorithme de sélection de pivot La médiane des médianes a la complexité de cas le plus défavorable pour O (N log (N)) , mais en raison de la surcharge qu’elle introduit, elle n’est pas utilisée dans la pratique. Il montre comment un bon algorithme de sélection peut modifier la complexité du cas le plus défavorable grâce à la sélection de pivot, théoriquement.


Que fait IntroSort?

IntroSort limite le twigment de QuickSort. C’est le point le plus important, cette limite est 2 * (log N) . Lorsque la limite est atteinte, IntroSort peut utiliser tout algorithme de sorting qui présente la complexité la plus défavorable de O (N log (N)).

Le twigment s’arrête lorsque nous avons des sous-problèmes O (log N). Nous pouvons résoudre tous les sous-problèmes O (n log n). (N minuscule représente les tailles de sous-problèmes).

La sum de (n log n) est notre pire cas de complexité, maintenant.

Pour le pire cas de QuickSort; supposons que nous avons un tableau déjà sortingé, et nous sélectionnons toujours le premier élément de ce tableau comme pivot. À chaque itération, nous ne nous débarrassons que du premier élément. Si nous continuions jusqu’à la fin, ce serait O (N ^ 2) évidemment. Avec IntroSort, nous arrêtons QuickSort, lorsque nous atteignons un journal de profondeur (N) , nous utilisons HeapSort pour le tableau non sortingé restant.

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

Résumez-les;

Jusqu’à ce que les twigments s’arrêtent, N + (N - 1) + ... + (N - log(N)) opérations effectuées. Au lieu d’utiliser gauss pour résumer, on peut simplement dire N + (N - 1) + ... + (N - log(N)) < N log(N) .

La partie HeapSort est (N - log(N)) log(N - log(N)) < N log(N)

Complexité globale < 2 N log(N) .

Comme les constantes peuvent être omises, la complexité la plus défavorable d' IntroSort est O (N log (N)) .


Infos complémentaires : Le code source de l'implémentation GCC STL est ici . Sort fonction de Sort est à la ligne 5461 .

Correction: * L'implémentation Microsoft .NET * sort est IntroSort depuis 2012. Les informations connexes sont ici .