Est-ce que std::sort vérifie si un vecteur est déjà trié ?

Question

Je crois que la norme C++ pour std::sort ne garantit pas des performances O(n) sur une liste déjà triée. Mais tout de même, je me demande si, à votre connaissance, les implémentations de la STL (GCC, MSVC, etc.) font le choix de la méthode de tri de la liste. std::is_sorted vérifier avant d'exécuter l'algorithme de tri ?

En d'autres termes, quelles sont les performances que l'on peut attendre (sans garantie, bien sûr) de l'exécution d'un programme de type std::sort sur un conteneur trié ?

Note complémentaire : j'ai posté quelques points de repère pour GCC 4.5 avec C++0x activé sur mon blog. Voici les résultats :

Answer 1

Les implémentations sont libres d'utiliser tout algorithme de tri efficace qu'elles souhaitent, ce qui dépend fortement de l'implémentation.

Cependant, j'ai vu une comparaison des performances de libstdc++ tel qu'utilisé sur linux et contre libc++ la nouvelle bibliothèque C++ développée par Apple/LLVM. Ces deux bibliothèques sont très efficaces sur des données triées ou triées à l'envers (beaucoup plus rapidement que sur une liste aléatoire), la nouvelle bibliothèque étant considérablement plus rapide que l'ancienne et reconnaissant beaucoup plus de modèles.

Pour en être certain, vous devriez envisager de faire vos propres tests de référence.

Answer 2

Non . De plus, il n'est pas logique d'avoir is_sorted() appelé pour toute implémentation STL. Depuis, is_sorted() est déjà disponible en version autonome. Et de nombreux utilisateurs peuvent ne pas vouloir gaspiller inutilement des cycles d'exécution pour appeler cette fonction lorsqu'ils savent déjà que leur conteneur n'est pas trié.

La STL devrait également suivre la philosophie du C++ : " paiement à l'utilisation ".

Answer 3

Wow ! Est-ce que tu as optimisé au maximum ?

les résultats de votre code sur ma plateforme (notez les valeurs sur l'axe vertical).

Answer 4

Je vous suggère de lire cette comparaison des algorithmes de tri Il compare un certain nombre d'algorithmes de tri entre eux et avec l'implémentation de std::sort par GCC. Vous remarquerez, dans les graphiques sur le lien donné, que les performances de std::sort pour "presque trié" et "presque inversé" sont linéaires dans le nombre d'éléments à trier, c'est-à-dire O(n). Donc, pas de garantie, mais vous pouvez facilement vous attendre à ce qu'une liste presque triée soit triée en temps presque linéaire. Mais, bien sûr, il ne fait pas de vérification is_sorted, et même s'il trie un tableau trié en temps linéaire, ce ne sera pas aussi rapide que de faire une vérification is_sorted et de sauter complètement le tri. C'est à vous de déterminer s'il est préférable de vérifier avant de trier ou non.

Answer 5

La norme sanctionne uniquement std::sort implémentations avec une complexité O(n log n) :

La complexité : Approximativement N log N (où N == last - first ) comparaisons sur la moyenne.

Voir la section 25.3.1.1 Le tri [lib.sort] (ISO/IEC 14882:2003(E)).

Ainsi, l'ensemble des fonctions de tri autorisées est limité, et vous avez raison de dire que cela ne garantit pas une complexité linéaire.

Le comportement idéal pour un tri est O(n), mais cela n'est pas possible dans le cas moyen.

Bien sûr, le cas moyen n'est pas nécessairement le cas exact que vous avez en ce moment, donc pour les cas particuliers, il n'y a pas beaucoup de garantie.