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

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

À une autre question, quelle performance peut-on attendre (sans garanties, bien sûr) de l’exécution de std::sort sur un conteneur sortingé?

Note latérale: j’ai posté des points de repère pour GCC 4.5 avec C ++ 0x activé sur mon blog. Voici les résultats:

Comparaison de std :: sort et std :: is_sorted

Les implémentations sont libres d’utiliser n’importe quel algorithme de sorting efficace, ce qui la rend hautement dépendante de l’implémentation.

Cependant, j’ai vu une comparaison des performances de libstdc ++ utilisée 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 les données sortingées ou inversement (beaucoup plus rapidement que sur une liste aléatoire), la nouvelle bibliothèque étant beaucoup plus rapide que l’ancienne et reconnaissant bien plus de modèles.

Pour être certain, vous devriez envisager de faire vos propres points de repère.

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

STL devrait également suivre la philosophie C ++: ” pay per use “.

Hou la la! Avez-vous eu des optimisations jusqu’au bout?

Voici les résultats de votre code sur ma plate-forme (notez les valeurs sur l’axe vertical).

Je vous suggère de lire cette comparaison des algorithmes de sorting . Elle est très bien faite et informative. Elle compare un certain nombre d’algorithmes de sorting les uns aux autres et à l’implémentation de std :: sort par GCC. Vous remarquerez, dans les graphiques du lien donné, que les performances de std :: sort pour “presque sortingé” et “presque inversé” sont linéaires dans le nombre d’éléments à sortinger, c’est-à-dire O (n). Donc, aucune garantie, mais vous pouvez facilement vous attendre à ce qu’une liste presque sortingée soit sortingée en temps quasi linéaire. Mais, bien sûr, il ne fait pas de vérification is_sorted, et même s’il sortingera un tableau sortingé dans le temps linéaire, il ne sera pas aussi rapide que d’effectuer une vérification is_sorted et d’omettre le sorting. C’est à vous de décider s’il est préférable de vérifier avant de sortinger ou non.

La norme ne sanctionne que les implémentations std::sort de complexité O (n log n):

Complexité: environ N log N (où N == last - first ) comparaisons en moyenne.

See section 25.3.1.1 Tri [lib.sort] (ISO / CEI 14882: 2003 (E)).

Ainsi, l’ensemble des fonctions de sorting autorisées est limité et vous avez raison de dire qu’il ne garantit pas la complexité linéaire.

Le comportement idéal pour une sorte est O (n), mais ce 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. Par conséquent, dans les cas difficiles, il n’ya pas vraiment de garantie.

Et pourquoi toute mise en œuvre ferait-elle cette vérification? Que gagnerait-il? – Rien en moyenne. Une bonne règle de conception consiste à ne pas encombrer la mise en œuvre avec des optimisations pour les cas critiques qui ne font aucune différence en moyenne. Cet exemple est similaire à la vérification de l’auto-affectation. Une réponse simple: ne le faites pas.

Il n’y a aucune garantie que ça va vérifier ça. Certaines implémentations le feront, d’autres pas.

Cependant, si vous pensez que votre entrée est peut-être déjà sortingée (ou presque sortingée), std::stable_sort peut être une meilleure option.