Comment implémenter des algorithmes de tri classiques en C ++ moderne?

L' std::sortalgorithme (et ses cousins std::partial_sortet std::nth_element) de la bibliothèque standard C ++ est dans la plupart des implémentations une fusion compliquée et hybride d'algorithmes de tri plus élémentaires , tels que le tri par sélection, le tri par insertion, le tri rapide, le tri par fusion ou le tri par tas.

Il existe de nombreuses questions ici et sur des sites sœurs tels que https://codereview.stackexchange.com/ liés aux bogues, à la complexité et à d'autres aspects de la mise en œuvre de ces algorithmes de tri classiques. La plupart des implémentations proposées consistent en des boucles brutes, utilisent la manipulation d'index et des types concrets, et sont généralement non triviales à analyser en termes d'exactitude et d'efficacité.

Question : comment mettre en œuvre les algorithmes de tri classiques mentionnés ci-dessus en utilisant le C ++ moderne?

• pas de boucles brutes , mais en combinant les blocs de construction algorithmiques de la bibliothèque standard de<algorithm>
• interface itérateur et utilisation de modèles au lieu de la manipulation d'index et de types concrets
• Style C ++ 14 , y compris la bibliothèque standard complète, ainsi que des réducteurs de bruit syntaxiques tels que des autoalias de modèle, des comparateurs transparents et des lambdas polymorphes.

Remarques :

• pour d'autres références sur les implémentations d'algorithmes de tri, voir Wikipedia , Rosetta Code ou http://www.sorting-algorithms.com/
• selon les conventions de Sean Parent (diapo 39), une boucle brute est une forboucle plus longue que la composition de deux fonctions avec un opérateur. Donc, f(g(x));ou f(x); g(x);ou f(x) + g(x);ne sont pas des boucles brutes, ni les boucles dans selection_sortet en insertion_sortdessous.
• Je suis la terminologie de Scott Meyers pour désigner le C ++ 1y actuel déjà comme C ++ 14, et pour désigner C ++ 98 et C ++ 03 à la fois comme C ++ 98, alors ne me flambez pas pour cela.
• Comme suggéré dans les commentaires de @Mehrdad, je fournis quatre implémentations en tant qu'exemple en direct à 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, je dénote les différences syntaxiques et de bibliothèque où les différentes versions linguistiques diffèrent.

Blocs de construction algorithmiques

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

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• les outils d'itérateur tels que non-membre std::begin()/ std::end()ainsi qu'avec std::next()sont disponibles uniquement à partir de C ++ 11 et au-delà. Pour C ++ 98, il faut les écrire lui-même. Il existe des substituts de Boost.Range dans boost::begin()/ boost::end()et de Boost.Utility dans boost::next().
• l' std::is_sortedalgorithme n'est disponible que pour C ++ 11 et au-delà. Pour C ++ 98, cela peut être implémenté en termes de std::adjacent_findet un objet fonction écrit à la main. Boost.Algorithm fournit également un boost::algorithm::is_sortedcomme substitut.
• l' std::is_heapalgorithme n'est disponible que pour C ++ 11 et au-delà.

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'itérateur. 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 les algorithmes de tri qui prennent <comme comparaison et ceux qui ont un objet de fonction de comparaison défini par l'utilisateur.

template<class It, class Compare = std::less<>>
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 le type de valeur d'un itérateur qui ajoute un encombrement mineur aux signatures des algorithmes de tri:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

En C ++ 98, il faut écrire deux surcharges et utiliser la typename xxx<yyy>::typesyntaxe verbeuse

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• Une autre particularité syntaxique est que C ++ 14 facilite l'encapsulation de comparateurs définis par l'utilisateur à travers des lambdas polymorphes (avec des autoparamètres qui sont déduits comme des arguments de modèle de fonction).
• C ++ 11 n'a que des lambdas monomorphes, qui nécessitent l'utilisation de l'alias de modèle ci-dessus value_type_t.
• En C ++ 98, il faut soit écrire un objet fonction autonome, soit recourir au type verbeux std::bind1st/ std::bind2nd/ std::not1de la syntaxe.
• Boost.Bind améliore cela avec la syntaxe boost::bindet _1/ _2placeholder.
• C ++ 11 et au-delà l'ont également std::find_if_not, alors que C ++ 98 a besoin std::find_ifd'un std::not1autour d'un objet 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 Modern Modern C ++ de Scott Meyers et GotW remanié par Herb Sutter . J'utilise les recommandations de style suivantes:

• Herb Sutter "Almost Always Auto" et Scott Meyers "Prefer auto to specific type declarations" recommendation, pour lesquels la brièveté est inégalée, bien que sa clarté soit parfois contestée .
• "Distinguer ()et {}lors de la création d'objets" de Scott Meyers et choisir systématiquement l'initialisation contreventement {}au lieu de la bonne vieille initialisation entre parenthèses ()(afin de contourner tous les problèmes d'analyse les plus vexants dans le code générique).
• Scott Meyers's "Prefer alias declarations to typedefs" . Pour les modèles, c'est un must de toute façon, et l'utiliser partout au lieu de typedefgagner du temps et ajoute de la cohérence.
• J'utilise un for (auto it = first; it != last; ++it)modèle à certains endroits, afin de permettre la vérification invariante de boucle pour les sous-plages déjà triées. Dans le code de production, l'utilisation de while (first != last)et ++firstquelque part dans la boucle peut être légèrement meilleure.

Tri de sélection

Le tri de sélection ne s'adapte en aucune façon aux données, donc son exécution est toujoursO(N²). Cependant, le tri par sélection a la propriété de minimiser le nombre de swaps . Dans les applications où le coût d'échange d'éléments est élevé, le tri par sélection peut très bien être l'algorithme de choix.

Pour l'implémenter à l'aide de la bibliothèque standard, utilisez std::min_elementà plusieurs reprises pour trouver l'élément minimum restant et iter_swappour le mettre en place:

template<class FwdIt, class Compare = std::less<>>
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_sortla plage déjà traitée est [first, it)triée comme invariant de boucle. Les exigences minimales sont des itérateurs directs , par rapport aux std::sortitérateurs à accès aléatoire de.

Détails omis :

• le tri de la sélection peut être optimisé avec un test précoce if (std::distance(first, last) <= 1) return;(ou pour les itérateurs directs / bidirectionnels:) if (first == last || std::next(first) == last) return;.
• pour les itérateurs 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 étant l'élément restant minimal et ne nécessite pas de swap.

Tri par insertion

Bien qu'il s'agisse de l'un des algorithmes de tri élémentaires avec le O(N²)pire des cas, le tri par insertion est l'algorithme de choix lorsque les données sont presque triées (car elles sont adaptatives ) ou lorsque la taille du problème est petite (car elle a une faible surcharge). Pour ces raisons, et parce qu'il est également stable , le tri par insertion est souvent utilisé comme cas de base récursif (lorsque la taille du problème est faible) pour des algorithmes de tri avec division et conquête plus élevés, tels que le tri par fusion ou le tri rapide.

Pour implémenter insertion_sortavec la bibliothèque standard, utilisez std::upper_boundà plusieurs reprises pour trouver l'emplacement où l'élément actuel doit aller et utilisez std::rotatepour déplacer les éléments restants vers le haut dans la plage d'entrée:

template<class FwdIt, class Compare = std::less<>>
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_sortla plage déjà traitée est [first, it)triée comme invariant de boucle. Le tri par insertion fonctionne également avec les itérateurs avancés.

Détails omis :

• le tri par insertion peut être optimisé avec un test précoce if (std::distance(first, last) <= 1) return;(ou pour les itérateurs directs / bidirectionnels:) if (first == last || std::next(first) == last) return;et une boucle sur l'intervalle [std::next(first), last), car le premier élément est garanti d'être en place et ne nécessite pas de rotation.
• pour les itérateurs bidirectionnels , la recherche binaire pour trouver le point d'insertion peut être remplacée par une recherche linéaire inversée en utilisant l' std::find_if_notalgorithme de la bibliothèque 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<BiDirIt>;
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 O(N²)comparaisons, mais cela améliore les O(N)comparaisons pour les entrées presque triées. La recherche binaire utilise toujours des O(N log N)comparaisons.
• Pour les petites plages d'entrée, la meilleure localité de mémoire (cache, prélecture) d'une recherche linéaire peut également dominer une recherche binaire (il faut bien sûr le tester).

Tri rapide

Lorsqu'il est soigneusement mis en œuvre, le tri rapide est robuste et a la O(N log N)complexité attendue, mais avec la O(N²)pire des situations qui peut être déclenchée avec des données d'entrée choisies de manière opposée. Lorsqu'un tri stable n'est pas nécessaire, le tri rapide est un excellent tri à usage général.

Même pour les versions les plus simples, le tri rapide est un peu plus compliqué à implémenter à l'aide de la bibliothèque standard que les autres algorithmes de tri classiques. L'approche ci-dessous utilise quelques utilitaires d'itérateur pour localiser l' élément central de la plage d'entrée [first, last)comme pivot, puis utilisez deux appels à std::partition(qui sont O(N)) pour partitionner à trois voies la plage d'entrée en segments d'éléments plus petits, égaux à, et plus grand que le pivot sélectionné, respectivement. Enfin, les deux segments externes avec des éléments plus petits et plus grands que le pivot sont triés récursivement:

template<class FwdIt, class Compare = std::less<>>
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 tri rapide est plutôt difficile à obtenir correctement et efficacement, car chacune des étapes ci-dessus doit être soigneusement vérifiée et optimisée pour le code au niveau de la production. En particulier, pour la O(N log N)complexité, le pivot doit se traduire par une partition équilibrée des données d'entrée, qui ne peut pas être garantie en général pour un O(1)pivot, mais qui peut être garantie si l'on définit le pivot comme la O(N)médiane 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 est O(N^2)complexe pour l' entrée " tuyau d'orgue " 1, 2, 3, ..., N/2, ... 3, 2, 1(car le milieu est toujours plus grand que tous les autres éléments).
• La sélection du pivot médian sur 3 à partir d' éléments choisis au hasard dans la plage d'entrée protège contre les entrées presque triées pour lesquelles la complexité se détériorerait autrementO(N^2).
• Le partitionnement à 3 voies (séparant les éléments plus petits, égaux et plus grands que le pivot) comme le montrent les deux appels àstd::partitionn'est pas l'O(N)algorithmele plus efficacepour obtenir ce résultat.
• pour les itérateurs à accès aléatoire , une O(N log N)complexité garantie peut être obtenue grâce à la sélection de pivot médian à l' aide std::nth_element(first, middle, last), 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 O(N)complexité de std::nth_elementpeut être plus cher que celui de la O(1)complexité d'un pivot médian de 3 suivi d'un O(N)appel à std::partition(qui est un passage direct unique compatible avec le cache les données).

Tri par fusion

Si l'utilisation O(N)d'espace supplémentaire n'est pas un problème, le tri par fusion est un excellent choix: c'est le seul algorithme de tri stable O(N log N) .

Il est simple à implémenter à l'aide d'algorithmes standard: utilisez quelques utilitaires d'itérateur pour localiser le milieu de la plage d'entrée [first, last)et combinez deux segments triés récursivement avec a std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
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 tri par fusion nécessite des itérateurs bidirectionnels, le goulot d'étranglement étant le std::inplace_merge. Notez que lors du tri des listes liées, le tri par fusion ne nécessite qu'un O(log N)espace supplémentaire (pour la récursivité). Ce dernier algorithme est implémenté par std::list<T>::sortdans la bibliothèque standard.

Tri par tas

Le tri par segment est simple à implémenter, effectue unO(N log N)tri sur place, mais n'est pas stable.

La première boucle, O(N)phase "heapify", met le tableau en ordre de tas. La deuxième boucle, la O(N log Nphase de "tri", extrait à plusieurs reprises le maximum et restaure l'ordre du tas. La bibliothèque standard rend cela extrêmement simple:

template<class RandomIt, class Compare = std::less<>>
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));
}

Dans le cas où vous considérez qu'il est "tricheur" d'utiliser std::make_heapet std::sort_heap, vous pouvez aller plus loin et écrire ces fonctions vous-même en termes de std::push_heapet std::pop_heap, respectivement:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
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<class RandomIt, class Compare = std::less<>>
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 à la fois push_heapet en pop_heaptant que complexité O(log N). Notez cependant que la boucle externe sur la plage [first, last)entraîne une O(N log N)complexité pour make_heap, alors qu'elle std::make_heapn'a qu'une O(N)complexité. Pour la O(N log N)complexité globale de heap_sortcelui-ci n'a pas d'importance.

Détails omis : O(N)implémentation demake_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 censées être exhaustives ou rigoureuses). Notez juste les énormes différences dans le LOC: C ++ 11 / C ++ 14 ont besoin d'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 ça valait le coup d'être partagé.

Tri par comptage

Bien qu'il soit assez spécialisé, le comptage du tri est un simple algorithme de tri des entiers et peut souvent être très rapide à condition que les valeurs des entiers à trier ne soient pas trop éloignées. C'est probablement l'idéal si l'on a besoin de trier une collection d'un million d'entiers connus pour être compris entre 0 et 100 par exemple.

Pour implémenter un tri de comptage très simple qui fonctionne avec des entiers signés et non signés, il faut trouver les éléments les plus petits et les plus grands dans la collection à trier; leur différence indiquera la taille du tableau de comptes à allouer. 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 requis de chaque entier dans la collection d'origine.

template<typename ForwardIterator>
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<ForwardIterator>::difference_type;
    std::vector<difference_type> 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 que cela ne soit utile que lorsque la plage des entiers à trier est connue pour être petite (généralement pas plus grande que la taille de la collection à trier), rendre le tri plus générique le rendrait plus lent dans ses meilleurs cas. Si la plage n'est pas connue pour être petite, un autre algorithme tel qu'un tri radix , ska_sort ou spreadsort peut être utilisé à la place.

Détails omis :

• Nous aurions pu passer les limites de la plage de valeurs acceptées par l'algorithme comme paramètres pour nous débarrasser totalement du premier std::minmax_elementpassage dans la collection. Cela rendra l'algorithme encore plus rapide lorsqu'une limite de plage utilement petite est connue par d'autres moyens. (Cela ne doit pas être exact; passer une constante de 0 à 100 est toujours bien mieux 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 à 1000 en vaut la peine; le les éléments supplémentaires sont écrits une fois avec zéro et lus une fois).

• Grandir countsà la volée est une autre façon d'éviter un premier passage séparé. Le fait de doubler la countstaille chaque fois qu'il doit croître donne du temps O (1) amorti par élément trié (voir l'analyse des coûts d'insertion de table de hachage pour la preuve que la croissance exponentielle est la clé). Grandir à la fin pour un nouveau maxest facile avec l' std::vector::resizeajout de nouveaux éléments mis à zéro. Le changement minà la volée et l'insertion de nouveaux éléments mis à zéro à l'avant peuvent être effectués std::copy_backwardaprès la croissance du vecteur. Puis mettre std::fillà zéro les nouveaux éléments.

• La countsboucle d'incrémentation est un histogramme. Si les données sont susceptibles d'être hautement répétitives et que le nombre de compartiments est petit, il peut être utile de dérouler sur plusieurs baies pour réduire le goulot d'étranglement de la dépendance des données de sérialisation du stockage / rechargement dans le même compartiment. Cela signifie plus de comptes à zéro au début et plus à boucler à la fin, mais cela en vaut la peine sur la plupart des processeurs pour notre exemple de millions de 0 à 100 nombres, surtout si l'entrée peut déjà être (partiellement) triée et ont de longues séries du même nombre.

• Dans l'algorithme ci-dessus, nous utilisons une min == maxvérification pour retourner tôt lorsque chaque élément a la même valeur (auquel cas la collection est triée). Il est en fait possible de vérifier complètement si la collection est déjà triée tout en trouvant les valeurs extrêmes d'une collection sans perte de temps supplémentaire (si le premier passage est toujours goulot d'étranglement avec le travail supplémentaire de mise à jour min et max). Cependant, un tel algorithme n'existe pas dans la bibliothèque standard et en écrire un serait plus fastidieux que d'écrire le reste du comptage lui-même. Il est laissé comme exercice au lecteur.

• Étant donné que l'algorithme ne fonctionne qu'avec des valeurs entières, des assertions statiques peuvent ê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_tpeut être préféré.

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