Comment implémenter les algorithmes de sorting classiques en C ++ moderne?

L’algorithme std::sort (et ses cousins std::partial_sort et std::nth_element ) de la bibliothèque standard C ++ est dans la plupart des implémentations une fusion complexe et hybride d’algorithmes de sorting plus élémentaires , tels que le sorting de sélection, le sorting par insertion, le sorting rapide , sortinge par fusion ou sorting par tas.

Il existe de nombreuses questions ici et sur des sites similaires tels que https://codereview.stackexchange.com/ liés aux bogues, à la complexité et à d’autres aspects des implémentations de ces algorithmes de sorting classiques. La plupart des implémentations proposées sont constituées de boucles brutes, utilisent la manipulation d’index et des types concrets, et sont généralement non sortingviales à parsingr en termes de correction et d’efficacité.

Question : comment les algorithmes de sorting classiques mentionnés ci-dessus peuvent-ils être implémentés en utilisant le C ++ moderne?

  • pas de boucles brutes , mais en combinant les blocs de construction algorithmiques de la bibliothèque standard de
  • interface d’iterator et utilisation de modèles au lieu de la manipulation d’index et des types de béton
  • Le style C ++ 14 , y compris la bibliothèque standard complète, ainsi que les réducteurs de bruit syntaxiques tels que auto alias auto , de modèles, les comparateurs transparents et les lambdas polymorphes.

Notes :

  • pour plus de références sur les implémentations des algorithmes de sorting, voir Wikipedia , Rosetta Code ou http://www.sorting-algorithms.com/
  • Selon les conventions de Sean Parent (diapositive 39), une boucle brute est une boucle for lo plus longue que la composition de deux fonctions avec un opérateur. Donc f(g(x)); ou f(x); g(x); f(x); g(x); ou f(x) + g(x); ne sont pas des boucles brutes et les boucles dans selection_sort et insertion_sort ne le sont pas non plus.
  • Je suis la terminologie de Scott Meyers pour dénoter le C ++ 1y actuel en C ++ 14, et pour désigner C ++ 98 et C ++ 03 en C ++ 98, ne me lancez pas pour cela.
  • Comme suggéré dans les commentaires de @Mehrdad, je propose quatre implémentations en tant qu’exemple Live à la fin de la réponse: C ++ 14, C ++ 11, C ++ 98 et Boost et C ++ 98.
  • La réponse elle-même est présentée en termes de C ++ 14 uniquement. Le cas échéant, j’indique les différences syntaxiques et de bibliothèque dans lesquelles les différentes versions linguistiques diffèrent.

Blocs constitutifs algorithmiques

Nous commençons par assembler les blocs de construction algorithmiques de la bibliothèque standard:

 #include  // min_element, iter_swap, // upper_bound, rotate, // partition, // inplace_merge, // make_heap, sort_heap, push_heap, pop_heap, // is_heap, is_sorted #include  // assert #include  // less #include  // distance, begin, end, next 
  • Les outils d’itération tels que std::begin() / std::end() et non-membre ainsi que std::next() ne sont disponibles qu’à partir de C ++ 11 et au-delà. Pour C ++ 98, il faut écrire eux-mêmes. Il y a des substituts de Boost.Range dans boost::begin() / boost::end() , et de Boost.Utility dans boost::next() .
  • std::is_sorted algorithme std::is_sorted est uniquement disponible pour C ++ 11 et les std::is_sorted . Pour C ++ 98, cela peut être implémenté en termes de std::adjacent_find et d’un object fonction écrit à la main. Boost.Algorithm fournit également un boost::algorithm::is_sorted comme substitut.
  • std::is_heap algorithme std::is_heap est uniquement disponible pour C ++ 11 et les std::is_heap .

Goodies syntaxiques

C ++ 14 fournit des comparateurs transparents de la forme std::less<> qui agissent de manière polymorphe sur leurs arguments. Cela évite d’avoir à fournir un type d’iterator. Cela peut être utilisé en combinaison avec les arguments de modèle de fonction par défaut de C ++ 11 pour créer une surcharge unique pour le sorting des algorithmes prenant comme comparaison et ceux qui ont un object de fonction de comparaison défini par l’utilisateur.

 template> void xxx_sort(It first, It last, Compare cmp = Compare{}); 

En C ++ 11, on peut définir un alias de modèle réutilisable pour extraire un type de valeur d’iterator qui ajoute un léger encombrement aux signatures des algorithmes de sorting:

 template using value_type_t = typename std::iterator_traits::value_type; template>> void xxx_sort(It first, It last, Compare cmp = Compare{}); 

En C ++ 98, il faut écrire deux surcharges et utiliser la typename xxx::type verbose typename xxx::type

 template void xxx_sort(It first, It last, Compare cmp); // general implementation template void xxx_sort(It first, It last) { xxx_sort(first, last, std::less::value_type>()); } 
  • Une autre finesse syntaxique est que C ++ 14 facilite l’encapsulation de comparateurs définis par l’utilisateur via des lambdas polymorphes (avec auto parameters auto déduits comme des arguments de modèles de fonctions).
  • C ++ 11 ne possède que des lambdas monomorphes, qui nécessitent l’utilisation de l’alias de modèle ci-dessus value_type_t .
  • Dans C ++ 98, il est nécessaire d’écrire un object fonction autonome ou de recourir au type de syntaxe std::bind1st / std::bind2nd / std::not1 .
  • Boost.Bind améliore ceci avec boost::bind et la syntaxe d’espace réservé _1 / _2 .
  • C ++ 11 et au-delà ont également std::find_if_not , alors que C ++ 98 nécessite std::find_if avec un std::not1 autour d’un object fonction.

Style C ++

Il n’y a pas encore de style C ++ 14 généralement acceptable. Pour le meilleur ou pour le pire, je suis de près le projet de Modern Meyers C ++ de Scott Meyers et le GotW remanié de Herb Sutter. J’utilise les recommandations de style suivantes:

  • “Almost Always Auto” de Herb Sutter et la recommandation de Scott Meyers “Prefer auto to specific type declarations” , pour lesquelles la brièveté est inégalée, bien que sa clarté soit parfois contestée .
  • Scott Meyers “Distinguish () et {} lors de la création d’objects” et choisit systématiquement l’initialisation par accolade {} au lieu de la bonne initialisation entre parenthèses () (pour contourner tous les problèmes les plus vexants dans le code générique).
  • Scott Meyers “préfère les déclarations d’alias aux typedefs” . Pour les modèles, c’est un must de toute façon, et l’utiliser partout au lieu de typedef gagner du temps et ajoute de la cohérence.
  • J’utilise un motif for (auto it = first; it != last; ++it) à certains endroits, afin de permettre une vérification invariante de la boucle pour les sous-gammes déjà sortingées. Dans le code de production, l’utilisation de while (first != last) et d’un ++first quelque part dans la boucle peut être légèrement meilleure.

Tri de sélection

Le sorting de sélection ne s’adapte en aucune façon aux données, de sorte que son exécution est toujours O(N²) . Cependant, le sorting par sélection a la propriété de minimiser le nombre de swaps . Dans les applications où le coût de l’échange des éléments est élevé, le sorting de sélection peut très bien constituer l’algorithme de choix.

Pour l’implémenter à l’aide de la bibliothèque standard, utilisez std::min_element à plusieurs resockets pour rechercher l’élément minimal restant et iter_swap pour le remplacer:

 template> void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { for (auto it = first; it != last; ++it) { auto const selection = std::min_element(it, last, cmp); std::iter_swap(selection, it); assert(std::is_sorted(first, std::next(it), cmp)); } } 

Notez que selection_sort a la plage déjà traitée [first, it) sortingée comme son invariant de boucle. Les exigences minimales sont les iterators directs , comparés aux iterators à access aléatoire de std::sort .

Détails omis :

  • Le sorting par sélection peut être optimisé avec un test précoce if (std::distance(first, last) < = 1) return; (ou pour les iterators avant / bidirectionnels: if (first == last || std::next(first) == last) return; ).
  • pour les iterators bidirectionnels , le test ci-dessus peut être combiné avec une boucle sur l'intervalle [first, std::prev(last)) , car le dernier élément est garanti comme élément minimal restant et ne nécessite pas de swap.

Tri par insertion

Bien qu’il s’agisse de l’un des algorithmes de sorting élémentaires avec le O(N²) plus défavorable O(N²) , le sorting par insertion est l’algorithme de choix lorsque les données sont presque sortingées (parce qu’elles sont adaptatives ) ou frais généraux bas). Pour ces raisons, et comme il est également stable , le sorting par insertion est souvent utilisé comme cas de base récursif (lorsque la taille du problème est faible) pour des algorithmes de sorting plus importants tels que le sorting par fusion ou le sorting rapide.

Pour implémenter insertion_sort avec la bibliothèque standard, utilisez std::upper_bound à plusieurs resockets pour trouver l'emplacement où l'élément actuel doit être utilisé, et utilisez std::rotate pour déplacer les éléments restants vers le haut dans la plage d'entrée:

 template> void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { for (auto it = first; it != last; ++it) { auto const insertion = std::upper_bound(first, it, *it, cmp); std::rotate(insertion, it, std::next(it)); assert(std::is_sorted(first, std::next(it), cmp)); } } 

Notez que insertion_sort a la plage déjà traitée [first, it) sortingée comme son invariant de boucle. Le sorting par insertion fonctionne également avec les iterators avant.

Détails omis :

  • Le sorting par insertion peut être optimisé avec un test précoce if (std::distance(first, last) < = 1) return; (ou pour les iterators avant / bidirectionnels: if (first == last || std::next(first) == last) return; ) et une boucle sur l'intervalle [std::next(first), last) , car le le premier élément est garanti pour être en place et ne nécessite pas de rotation.
  • pour les iterators bidirectionnels , la recherche binary pour trouver le point d'insertion peut être remplacée par une recherche linéaire inverse à l' aide de l'algorithme std::find_if_not la std::find_if_not standard.

Quatre exemples en direct ( C ++ 14 , C ++ 11 , C ++ 98 et Boost , C ++ 98 ) pour le fragment ci-dessous:

 using RevIt = std::reverse_iterator; auto const insertion = std::find_if_not(RevIt(it), RevIt(first), [=](auto const& elem){ return cmp(*it, elem); } ).base(); 
  • Pour les entrées aléatoires, cela donne des comparaisons O(N²) , mais cela améliore les comparaisons O(N) pour les entrées presque sortingées. La recherche binary utilise toujours les comparaisons O(N log N) .
  • Pour les petites plages d'entrée, la meilleure localisation de la mémoire (cache, lecture préalable) d'une recherche linéaire pourrait également dominer une recherche binary (il convient bien sûr de tester cela).

Tri rapide

Lorsqu'il est soigneusement implémenté, le sorting rapide est robuste et a la complexité attendue O(N log N) , mais avec la complexité du pire cas O(N²) qui peut être déclenchée avec des données d'entrée choisies de manière défavorable. Lorsqu'un sorting stable n'est pas nécessaire, le sorting rapide est un excellent moyen général.

Même pour les versions les plus simples, le sorting rapide est un peu plus compliqué à mettre en œuvre en utilisant la bibliothèque standard que les autres algorithmes de sorting classiques. L'approche ci-dessous utilise quelques utilitaires d'iterators pour localiser l' élément central de la plage d'entrée [first, last) tant que pivot, puis utiliser deux appels à std::partition (qui sont O(N) ) pour partitionner l'entrée en trois parties se diviser en segments d’éléments inférieurs, égaux ou supérieurs au pivot sélectionné, respectivement. Enfin, les deux segments externes avec des éléments plus petits et plus grands que le pivot sont sortingés récursivement:

 template> void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N < = 1) return; auto const pivot = *std::next(first, N / 2); auto const middle1 = std::partition(first, last, [=](auto const& elem){ return cmp(elem, pivot); }); auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ return !cmp(pivot, elem); }); quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp)); quick_sort(middle2, last, cmp); // assert(std::is_sorted(middle2, last, cmp)); } 

Cependant, le sorting rapide est assez délicat pour être correct et efficace, car chacune des étapes ci-dessus doit être soigneusement vérifiée et optimisée pour le code de niveau de production. En particulier, pour la complexité O(N log N) , le pivot doit aboutir à une partition équilibrée des données d'entrée, qui ne peut pas être garantie en général pour un pivot O(1) , mais qui peut être garantie si l'on définit le pivot comme la médiane O(N) de la plage d'entrée.

Détails omis :

  • la mise en œuvre ci-dessus est particulièrement vulnérable aux entrées spéciales, par exemple elle a une complexité O(N^2) pour les entrées 1, 2, 3, ..., N/2, ... 3, 2, 1 car le milieu est toujours plus grand que tous les autres éléments).
  • sélection du pivot médian sur 3 à partir d' éléments choisis au hasard parmi les gardes de la plage d'entrée contre des entrées presque sortingées pour lesquelles la complexité se détériorerait autrement pour atteindre O(N^2) .
  • Le partitionnement à trois voies (séparant les éléments plus petits que, égal ou supérieur au pivot), comme le montrent les deux appels à std::partition n'est pas l'algorithme O(N) le plus efficace pour obtenir ce résultat.
  • pour les iterators à access aléatoire , une sélection de pivotement médiane à l' aide de std::nth_element(first, middle, last) permet d'obtenir une complexité O(N log N) garantie, suivie d'appels récursifs à quick_sort(first, middle, cmp) et quick_sort(middle, last, cmp) .
  • cette garantie a cependant un coût, car le facteur constant de la complexité O(N) de std::nth_element peut être plus coûteux que celui de la complexité O(1) d'un pivot médian-3 suivi d'un O(N) appel à std::partition (qui est un simple passage vers l'avant compatible avec le cache sur les données).

Tri par fusion

Si l'utilisation de l'espace supplémentaire O(N) est sans importance, le sorting par fusion est un excellent choix: il s'agit du seul algorithme de sorting stable O(N log N) .

Il est simple à mettre en œuvre en utilisant des algorithmes standard: utilisez quelques utilitaires d'iterator pour localiser le milieu de la plage d'entrée [first, last) et combinez deux segments sortingés récursivement avec un std::inplace_merge :

 template> void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N < = 1) return; auto const middle = std::next(first, N / 2); merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp)); merge_sort(middle, last, cmp); // assert(std::is_sorted(middle, last, cmp)); std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp)); } 

Le sorting par fusion nécessite des iterators bidirectionnels, le goulot d'étranglement étant le std::inplace_merge . Notez que lors du sorting des listes liées, le sorting par fusion ne nécessite que de l'espace supplémentaire (pour la récursivité). Le dernier algorithme est implémenté par std::list::sort dans la bibliothèque standard.

Tri de tas

Le sorting du tas est simple à mettre en œuvre, effectue un sorting sur place O(N log N) , mais n'est pas stable.

La première boucle, O(N) "heapify" phase, met le tableau en ordre de tas. La seconde boucle, la phase de "sorting" O(N log N ), extrait de manière répétée le maximum et restaure l'ordre du tas. La bibliothèque standard rend cela extrêmement simple:

 template> void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{}) { lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp)); lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp)); } 

Si vous considérez qu'il faut sortingcher pour utiliser std::make_heap et std::sort_heap , vous pouvez aller plus loin et écrire ces fonctions vous-même en termes de std::push_heap et std::pop_heap , respectivement:

 namespace lib { // NOTE: is O(N log N), not O(N) as std::make_heap template> void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{}) { for (auto it = first; it != last;) { std::push_heap(first, ++it, cmp); assert(std::is_heap(first, it, cmp)); } } template> void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{}) { for (auto it = last; it != first;) { std::pop_heap(first, it--, cmp); assert(std::is_heap(first, it, cmp)); } } } // namespace lib 

La bibliothèque standard spécifie push_heap et pop_heap comme complexité O(log N) . Notez cependant que la boucle externe sur la plage [first, last) entraîne une complexité O(N log N) pour make_heap , alors que std::make_heap n'a que la complexité O(N) . Pour la complexité globale de O(N log N) de heap_sort cela n'a pas d'importance.

Détails omis : O(N) implémentation de make_heap

Essai

Voici quatre exemples en direct ( C ++ 14 , C ++ 11 , C ++ 98 et Boost , C ++ 98 ) testant les cinq algorithmes sur une variété d'entrées (non exhaustif ou rigoureux). Il suffit de noter les différences énormes dans le LOC: C ++ 11 / C ++ 14 nécessite environ 130 LOC, C ++ 98 et Boost 190 (+ 50%) et C ++ 98 plus de 270 (+ 100%).

Un autre petit et plutôt élégant trouvé à l’origine sur la revue de code . Je pensais que cela valait la peine d’être partagé.

Sorte de comptage

Bien qu’il soit plutôt spécialisé, le sorting par comptage est un algorithme simple de sorting par nombres entiers et peut souvent être très rapide, à condition que les valeurs des entiers à sortinger ne soient pas trop éloignées. C’est probablement l’idéal si l’on doit sortinger une collection d’un million d’entiers connus pour être entre 0 et 100 par exemple.

Pour implémenter un sorting de comptage très simple qui fonctionne à la fois avec des entiers signés et non signés, il faut trouver les éléments les plus petits et les plus grands de la collection à sortinger; leur différence indiquera la taille du tableau des comptes à atsortingbuer. Ensuite, un deuxième passage dans la collection est effectué pour compter le nombre d’occurrences de chaque élément. Enfin, nous réécrivons le nombre requirejs de chaque entier dans la collection d’origine.

 template void counting_sort(ForwardIterator first, ForwardIterator last) { if (first == last || std::next(first) == last) return; auto minmax = std::minmax_element(first, last); // avoid if possible. auto min = *minmax.first; auto max = *minmax.second; if (min == max) return; using difference_type = typename std::iterator_traits::difference_type; std::vector counts(max - min + 1, 0); for (auto it = first ; it != last ; ++it) { ++counts[*it - min]; } for (auto count: counts) { first = std::fill_n(first, count, min++); } } 

Bien qu’il ne soit utile que lorsque la gamme des entiers à sortinger est connue pour être petite (généralement pas plus grande que la taille de la collection à sortinger), rendre le décompte plus générique le rendrait plus lent dans les meilleurs cas. Si la plage n’est pas connue pour être petite, un autre algorithme, tel un sorting de base , ska_sort ou un tableur, peut être utilisé à la place.

Détails omis :

  • Nous aurions pu passer les limites de la plage de valeurs acceptées par l’algorithme en tant que parameters pour nous débarrasser totalement du premier passage std::minmax_element dans la collection. Cela rendra l’algorithme encore plus rapide lorsqu’une limite de scope utile est connue par d’autres moyens. (Il n’est pas nécessaire que ce soit exact; faire passer une constante de 0 à 100 est toujours bien meilleur qu’un passage supplémentaire sur un million d’éléments pour découvrir que les vraies limites sont de 1 à 95. Même 0 à 1 000 en vaut la peine; les éléments supplémentaires sont écrits une fois avec zéro et lus une fois).

  • Le nombre croissant à la volée est un autre moyen d’éviter un premier passage séparé. En doublant la taille de counts chaque croissance, on obtient le temps O (1) amorti par élément sortingé (voir Analyse des coûts d’insertion de table de hachage pour la preuve que la croissance exponentielle est la clé). La croissance à la fin d’un nouveau max est facile avec std::vector::resize pour append de nouveaux éléments remis à zéro. Changer min à la volée et insérer de nouveaux éléments mis à zéro au std::copy_backward peut être fait avec std::copy_backward après la croissance du vecteur. Alors std::fill pour mettre à zéro les nouveaux éléments.

  • La boucle d’incrémentation des counts est un histogramme. Si les données risquent d’être hautement répétitives et que le nombre de fichiers est petit, il peut être utile de dérouler sur plusieurs baies pour réduire le goulot d’étranglement de la dépendance entre les données et la sérialisation du stockage / rechargement dans le même conteneur. Cela signifie que plus de comptes à zéro au début, et plus à boucler à la fin, mais cela devrait valoir la peine sur la plupart des processeurs pour notre exemple de millions de numéros de 0 à 100, surtout si l’entrée peut être (partiellement) sortingée et avoir de longues courses du même numéro.

  • Dans l’algorithme ci-dessus, nous utilisons un contrôle min == max pour retourner tôt lorsque chaque élément a la même valeur (auquel cas la collection est sortingée). Il est en fait possible de vérifier complètement si la collection est déjà sortingée tout en recherchant les valeurs extrêmes d’une collection sans perte de temps supplémentaire (si la première passe est toujours goulot de mémoire avec le travail supplémentaire de mise à jour min et max). Cependant, un tel algorithme n’existe pas dans la bibliothèque standard et l’écriture serait plus fastidieuse que l’écriture du rest du sorting par comptage. Il est laissé comme exercice pour le lecteur.

  • Puisque l’algorithme ne fonctionne qu’avec des valeurs entières, des assertions statiques pourraient être utilisées pour empêcher les utilisateurs de faire des erreurs de type évidentes. Dans certains contextes, un échec de substitution avec std::enable_if_t pourrait être préféré.

  • Alors que le C ++ moderne est cool, le futur C ++ pourrait être encore plus cool: des liaisons structurées et certaines parties du TS des gammes rendraient l’algorithme encore plus propre.