Qui l'algorithme de tri utilisé par STL liste::sort()?

J'ai une liste d'entiers aléatoires. Je me demande qui est l'algorithme utilisé par le list::sort() méthode. E. g. dans le code suivant:

list<int> mylist;

//..insert a million values

mylist.sort();

EDIT: Voir aussi cette question plus spécifique.

InformationsquelleAutor sharkin | 2009-11-11
  1. 45

    La norme n'exige pas d'un algorithme particulier, mais seulement qu'il doit être stable, et qu'il complète le trier en utilisant environ N lg N comparaisons. Cela permet, par exemple, une fusion de tri ou d'une liste liée version d'un tri rapide (contrairement à la croyance populaire, tri rapide n'est pas nécessairement instable, même si la plus commune de mise en œuvre pour les tableaux est).

    Avec cette réserve, la réponse courte est que de la plupart des bibliothèques standard, std::sort est mis en œuvre comme une intro de tri (introspective de tri), qui est essentiellement un Quicksort qui conserve la trace de sa profondeur de récursion, et de passer à un Heapsort (généralement plus lent mais d'une garantie O(n log n) la complexité) si le tri rapide est d'utiliser de trop de profondeur de récursivité. Introsort a été inventé relativement récemment (fin des années 1990). Les anciennes bibliothèques standard généralement utilisé un Quicksort à la place.

    stable_sort existe parce que pour le tri de tableau-comme des conteneurs, la plupart de la plus rapide des algorithmes de tri sont instables, de sorte que le standard inclut à la fois std::sort (rapide mais pas nécessairement stable) et std::stable_sort (stable, mais souvent un peu plus lent).

    À la fois de ceux-ci, cependant, normalement s'attendre à accès aléatoire itérateurs, et fonctionne mal (voire pas du tout) avec quelque chose comme une liste chaînée. Pour obtenir des performances décentes pour les listes chaînées, la norme comprend list::sort. Pour une liste liée, cependant, il n'est pas vraiment un tel compromis -- il est assez facile à mettre en œuvre une fusion de tri qui est à la fois stable et (presque) aussi vite que toute autre chose. En tant que tels, ils ont juste besoin d'un sort fonction membre qui est nécessaire pour être stable.

    • Alors, pourquoi est-il un stable_sort dans la STL ?
    InformationsquelleAutor Jerry Coffin
  2. 14

    C'est complètement définie par l'implémentation. La seule chose que dit la norme, c'est que c'est la complexité est O(n lg n), et que le tri est stable. C'est, ordre relatif des éléments égaux est la garantie de ne pas changer après le tri.

    std::list's de tri de la fonction membre est généralement mis en œuvre en utilisant une certaine forme de fusion de tri, parce que la fusion de tri est stable, et les fusions sont vraiment vraiment bon marché lorsque vous travaillez avec des listes chaînées.

    Espère que cela aide 🙂

    InformationsquelleAutor Billy ONeal
  3. -2

    Bien est-il de la mise en œuvre/vendor dépendante, mais la plupart de la mise en œuvre je sais utilise Introsort dont le meilleur & pire des cas, la complexité est en O(nlogn).

    Référence:http://en.wikipedia.org/wiki/Introsort

    • Introsort n'est pas utilisé pour trier la liste.
    InformationsquelleAutor whacko__Cracko