Qu'est-ce que la complexité du temps de std::sort() dans la norme C++ de la bibliothèque?

Quelle est la complexité de std::sort() dans la Norme C++ de la Bibliothèque? Le tri est appliqué? Est-il de la règle de l'application de toute particulier algorithme de tri là?

InformationsquelleAutor Hari Chaudhary | 2010-12-19
  1. 28

    std::sort doit avoir moyen de cas linearithmic (n log n) le temps de la complexité. Tout algorithme peut être utilisé tant que le temps de la complexité exigence est respectée. Il n'est pas le cas le pire moment de la complexité exigence.

    Si vous voulez une garantie dans le cas le pire moment de la complexité de la fonction, l'utilisation std::stable_sort, qui a quasilinear pire des cas, la complexité temporelle (n log^2 n).

    • +1 pour me présenter à la parole "linearithmic" -- n'avais pas rencontré avant, mais il est certainement un gardien 🙂
    • Je ne connais pas le C++03, mais le C++0x projets de demandes O(n log n) pire des cas de la complexité. Et std::stable_sort est garanti pour s'exécuter en O(n log^2 n).
    • De sorte qu'il n'. C++03 déclare explicitement qu'il n'y a pas de pire-cas complexité. Je n'étais pas conscient que des changements ont été apportés à la C++0x algorithme de complexité dans C++0x. (Vous avez raison au sujet de partial_sort; il a seulement quasilinear complexité temporelle en C++03 et C++0x).
    InformationsquelleAutor James McNellis
  2. 5

    La complexité est O(n log n). Certaines communes implémentations utilisent introsort autant que je sache:

    http://en.wikipedia.org/wiki/Introsort

    • viens de lire sur introsort, assez cool. m'a rappelé une sorte avec quelqu'un prénom, mais je ne peux pas le trouver. nicksort, petesort, quelque chose comme ça. personne ne sait ce que cela s'appelle?
    • Vous pensez peut-être de Timsort. en.wikipedia.org/wiki/Timsort
    • je vous était. merci!
    InformationsquelleAutor Stuart Golodetz
  3. 5

    http://en.wikipedia.org/wiki/Sort_(C%2B%2B)

    Spécifiques algorithme de tri n'est pas obligatoire et peuvent varier selon les implémentations. La GNU Standard C++ library, par exemple, utilise un hybride algorithme de tri: introsort est réalisée en premier lieu, à une profondeur maximale donnée par 2×log2 n, où n est le nombre d'éléments, suivie par une insertion de tri sur le résultat.[1] Quelle que soit la mise en œuvre, la complexité doit être en O(n log n) comparaisons sur la base de la moyenne. [2]

    InformationsquelleAutor Adam Vandenberg
  4. 5

    La norme garantit

    Du C++11/14 standard, std::sort est la garantie d'avoir:

    §25.4.1.1/3

    Complexité: O(N log(N)) (où N == last - first) comparaisons.

    L'autre, stable, standard de l'algorithme de tri (à savoir std::stable_sort) est la garantie d'avoir:

    25.4.1.2/3

    Complexité: Il ne fait plus N log2(N) (où N == last - first), de comparaison, si suffisamment de mémoire supplémentaire est disponible, il est N log(N).

    Pour std::forward_list::stable, au lieu de:

    23.3.4.6/26

    Complexité: Environ N log(N) comparaisons, où N est distance(begin(), end()).

    Il en va de même pour std::list:

    23.3.5.5/31

    Complexité: Environ N log(N) comparaisons, où N == size().

    Algorithme de tri

    La norme C++ ne spécifie pas de quel algorithme de tri à appliquer dans l'un des cas ci-dessus. Ce serait souvent inutiles et la mise en œuvre de restriction.

    Si vous avez besoin de savoir vous pourriez avoir de la chance en regardant dans un compilateur spécifique de la spécification. Par exemple pour GNU GCC, vous commencerez ici.

    • De sorte que le pire de la complexité de std::sort() est également O(NlogN)?
    InformationsquelleAutor Shoe
  5. 1

    Si vous voulez dire std::sort():

    C'est à partir de C++03 standard, de l'article 25.3. La garantie de performance:

    template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last,
    Compare comp);

    1 Effets: Trie les éléments de l'intervalle [first, last).

    2 Complexité: Environ N log N (où N == dernier - premier) comparaisons sur la base de la moyenne.

    • désolé, copié l'intégralité extrait. last et first sont les itérateurs passé à sort.
    InformationsquelleAutor wkl
  6. 0

    La C++ standard spécifie que le le pire cas d'exécution de std::sort() est dans O(n log n) - où n est le nombre d'éléments triés (cf. C++11, Section 25.4.1.1).

    Le standard n'a pas de spécifier un algorithme de tri.

    Ainsi, conforme std::sort() mise en œuvre est libre de choisir n'importe quel algorithme qui satisfait à ces runtime exigence.

    Remarque que le C++ standard de révisions avant C++11 seulement requis que le moyenne runtime de std::sort() est dans O(n log n).

    Voir aussi la stackoverflow question Quels algorithmes sont utilisés en C++11 std::sort dans les différents STL implémentations? pour avoir une idée de quels algorithmes de tri sont utilisés dans le monde réel STL implémentations.

    InformationsquelleAutor maxschlepzig