Algorithme de tri | exemples d'algorithmes de tri

Exemples d'algorithmes de tri

Tris par comparaison

Algorithmes rapides

  • Tri fusion (merge sort) − dans tous les cas ; stable ; pas en place par défaut[3].
    Cet algorithme repose sur le principe « diviser pour régner ». Pour une entrée donnée, l'algorithme la divise en deux parties de tailles similaires, trie chacune d'entre elles en utilisant le même algorithme, puis fusionne les deux parties triées. Il se prête aussi bien à des implémentations sur listes que sur tableaux. Il est utilisé en particulier par l'algorithme hybride Timsort.
  • Tri rapide (quicksort) − en moyenne et dans le meilleur des cas, dans le pire des cas ; instable ; en place dans la variante de Sedgewick.
    Cette méthode repose sur le principe « diviser pour régner ». Une valeur est choisie comme pivot et les éléments plus petits que le pivot sont dissociés, par échanges successifs, des éléments plus grands que le pivot ; chacun de ces deux sous-ensembles est ensuite trié de la même manière. On peut rendre la complexité quasiment indépendante des données en utilisant un pivot aléatoire ou en appliquant au tableau une permutation aléatoire avant de le trier.
  • Tri par tas (heap sort) − dans tous les cas ; en place mais instable.
    Il s'agit d'une amélioration du tri par sélection. L'idée est la même (insérer les éléments un à un dans une structure déjà triée), mais l'algorithme utilise une structure de tas, souvent implémentée au moyen d'un tableau. Il est intéressant d'utiliser ce tri si l'on soupçonne que les données à trier constituent un cas dans lequel le tri rapide aurait une complexité quadratique.[pas clair]
  • Introsort dans tous les cas ; instable mais en place.
    Il s'agit d'un hybride du tri rapide et du tri par tas.
  • Tri arborescent en moyenne, dans le pire des cas, dans le meilleur des cas. ; ni stable ni en place.
    L'idée est d'insérer les éléments un à un dans un arbre binaire de recherche, puis de lire l'arbre selon un parcours en profondeur. Ce tri est un des plus lents (parmi les tris rapides) et un des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre quasi-linéaire dans tous les cas[Comment ?] en maintenant un arbre équilibré (c.f. Arbre AVL).
  • Smoothsort en moyenne et dans le pire des cas, dans le meilleur des cas ; en place mais instable.
    Tri inspiré du tri par tas, mais qui utilise un arbre non inversé[Quoi ?]. Ce tri est très rapide pour les ensembles déjà presque triés.

Pour un algorithme de tri donné instable, il est facile d'en obtenir une variante stable en utilisant un tableau supplémentaire pour mémoriser l'ordre initial des éléments. L'algorithme obtenu n'est toutefois pas en place.

Algorithmes moyennement rapides

  • Tri de Shell (shell sort) − pour la série de pas et pour la série de pas  ; instable ; en place.
    Ce tri repose sur le tri par insertion des sous-suites de l'entrée obtenues en prenant les éléments espacés d'un pas constant, pour une suite de pas prédéfinie. La complexité varie selon le choix de cette suite. On ne connaît pas de série donnant .
  • Tri fusion (merge sort) − dans tous les cas ; stable ; pas en place par défaut[3].
    Cet algorithme repose sur le principe « diviser pour régner ». Pour une entrée donnée, l'algorithme la divise en deux parties de tailles similaires, trie chacune d'entre elles en utilisant le même algorithme, puis fusionne les deux parties triées. Il se prête aussi bien à des implémentations sur listes que sur tableaux. Il est utilisé en particulier par l'algorithme hybride Timsort.
  • Tri rapide (quicksort) − en moyenne et dans le meilleur des cas, dans le pire des cas ; instable ; en place dans la variante de Sedgewick.
    Cette méthode repose sur le principe « diviser pour régner ». Une valeur est choisie comme pivot et les éléments plus petits que le pivot sont dissociés, par échanges successifs, des éléments plus grands que le pivot ; chacun de ces deux sous-ensembles est ensuite trié de la même manière. On peut rendre la complexité quasiment indépendante des données en utilisant un pivot aléatoire ou en appliquant au tableau une permutation aléatoire avant de le trier.
  • Tri par tas (heap sort) − dans tous les cas ; en place mais instable.
    Il s'agit d'une amélioration du tri par sélection. L'idée est la même (insérer les éléments un à un dans une structure déjà triée), mais l'algorithme utilise une structure de tas, souvent implémentée au moyen d'un tableau. Il est intéressant d'utiliser ce tri si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide.
  • Introsort dans tous les cas ; instable mais en place.
    Il s'agit d'un algorithme hybride utilisant les algorithmes de tri rapide et de tri par tas.
  • Tri arborescent en moyenne, dans le pire des cas, dans le meilleur des cas. ; ni stable ni en place.
    L'idée est d'insérer les éléments un à un dans un arbre binaire de recherche, puis de lire l'arbre selon un parcours en profondeur. Ce tri est un des plus lents (parmi les tris rapides) et un des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre quasi-linéaire dans tous les cas en maintenant un arbre équilibré (c.f. Arbre AVL).
  • Smoothsort en moyenne et dans le pire des cas, dans le meilleur des cas ; en place mais instable.
    Tri inspiré du tri par tas, mais qui utilise un arbre non inversé. Ce tri est très rapide pour les ensembles déjà presque triés.
  • Tri à peigne (comb sort) − dans le meilleur des cas, en moyenne et dans le pire des cas ; instable mais en place.
    Il s'agit d'une variante plus efficace du tri à bulles, ne comparant pas uniquement des éléments consécutifs. On peut dire qu'il est au tri à bulles ce que le tri de Shell est au tri par insertion.

Pour un algorithme de tri donné instable, il est facile d'en obtenir une variante stable en utilisant un tableau supplémentaire pour mémoriser l'ordre initial des éléments. L'algorithme obtenu n'est toutefois pas en place. ence en travaillant sur des listes).

  • Il s'agit, à chaque itération, d'identifier le plus petit des éléments qui ne sont pas encore triés, et de l'échanger avec le premier de ceux-ci. Ce tri est rapide pour des petites entrées, et se code de manière concise.
  • Tri par insertion en moyenne et dans le pire des cas, dans le meilleur des cas ; stable et en place.
    C'est le tri souvent utilisé naturellement pour trier des cartes à jouer : les valeurs sont insérées les unes après les autres dans une liste triée (initialement vide). C'est souvent le plus rapide et le plus utilisé pour trier des entrées de petite taille. Il est également efficace pour des entrées déjà presque triées.
  • Tri à bulles en moyenne et dans le pire des cas, dans le meilleur des cas ; stable et en place.
    L'algorithme consiste à parcourir l'entrée du début à la fin et, pour chaque couple d'éléments consécutifs, à les intervertir s'ils sont mal ordonnés. Cette opération est répétée jusqu'à ce que la structure soit triée (aucune interversion lors du dernier passage). Cet algorithme est peu efficace et rarement utilisé en pratique ; son intérêt est principalement pédagogique.
  • Tri cocktail en moyenne et dans le pire des cas, dans le meilleur des cas ; stable et en place.
    Il s'agit d'une variante du tri à bulles dans laquelle l'entrée est alternativement parcourue dans les deux sens. S'il permet de traiter de manière plus efficace quelques cas problématiques pour le tri à bulles, il reste essentiellement similaire à ce dernier et l'intérêt est encore une fois principalement pédagogique.
  • Tri pair-impair en moyenne et dans le pire des cas, dans le meilleur des cas ; stable et en place.
    Il s'agit d'une variante du tri à bulles, qui procède en comparant successivement tous les éléments d'index pairs avec les éléments d'index impairs qui les suivent, puis inversement. On va ainsi commencer en comparant le premier élément au second, le troisième au quatrième, etc., puis l'on comparera le second élément au troisième, le quatrième au cinquième etc. L'opération est répétée jusqu'à ce que la structure soit triée.

Algorithmes lents

Ces algorithmes ont une complexité asymptotique en et sont par conséquent considérés comme lents pour des entrées dont la taille est de plus de quelques dizaines d'éléments.

  • Tri par sélection dans tous les cas ; sur place ; instable par défaut (peut être rendu stable, mais de préférence en travaillant sur des listes).

Algorithmes très lents

Ces algorithmes ont une complexité asymptotique moins bonne que , qui est la complexité des algorithmes les plus intuitifs.

  • Tri stupide − Ne termine pas dans le pire des cas, en moyenne et dans le meilleur des cas ; instable mais en place.
    Le tri stupide consiste à vérifier si les éléments sont ordonnés et s'ils ne le sont pas à mélanger aléatoirement les éléments, puis à répéter l'opération.
  • Tri faire-valoir (stooge sort) - soit approximativement  ; instable et pas en place[réf. nécessaire].
    Ce tri consiste à échanger si nécessaire le premier et le dernier élément, puis à trier récursivement les deux premiers tiers, puis les deux derniers, puis de nouveau les deux premiers du tableau.

Tris utilisant la structure des données

  • Tri comptage ou tri par dénombrement (counting sort) : Algorithme linéaire, T(n) = O(n), stable mais nécessite l'utilisation d'une seconde liste de même longueur que la liste à trier. Son utilisation relève de la condition que les valeurs à trier sont des entiers naturels dont on connaît les extrema ;
  • Tri par base (radix sort) : c'est aussi un tri linéaire dans certaines conditions (moins restrictives que pour le tri par comptage), T(n) = O(n), stable mais nécessite aussi l'utilisation d'une seconde liste de même longueur que la liste à trier ;
  • Tri par paquets (bucket sort) : Stable et en complexité linéaire -- , part de l'hypothèse que les données à trier sont réparties de manière uniforme sur un intervalle réel .

Tris externes

Les algorithmes de tri doivent aussi être adaptés en fonction des configurations informatiques sur lesquels ils sont utilisés. Dans les exemples cités plus haut, on suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en mémoire virtuelle). La situation se complexifie si l'on veut trier des volumes de données supérieurs à la mémoire centrale disponible (ou si l'on cherche à améliorer le tri en optimisant l'utilisation de la hiérarchie de mémoire).

Ces algorithmes sont souvent basés sur une approche assez voisine de celle du tri fusion. Le principe est le suivant :

  • découpage du volume de données à trier en sous-ensembles de taille inférieure à la mémoire rapide disponible ;
  • tri de chaque sous-ensemble en mémoire centrale pour former des « monotonies » (sous-ensembles triés) ;
  • interclassement des monotonies.
Other Languages
azərbaycanca: Nİzamlama alqoritmi
Bahasa Indonesia: Algoritme penyortiran
日本語: ソート
Lëtzebuergesch: Zortéieralgorithmus
олык марий: Ойыркалымаш
Nederlands: Sorteeralgoritme
polski: Sortowanie
Simple English: Sorting algorithm
中文: 排序算法