Algorithme de tri

 Ne doit pas être confondu avec tri topologique.

Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche par dichotomie. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur.

La collection à trier est souvent donnée sous forme de tableau, afin de permettre l' accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et à l'usage de la programmation fonctionnelle.

Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la relation d’ordre associée. Un même algorithme peut par exemple être utilisé pour trier des réels selon la relation d'ordre usuelle « est inférieur ou égal à » et des chaînes de caractères selon l' ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe.

Les algorithmes de tri sont souvent étudiés dans les cours d' algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison.

Critères de classification

La classification des algorithmes de tri est très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci. Les principales caractéristiques qui permettent de différencier les algorithmes de tri, outre leur principe de fonctionnement, sont la complexité temporelle, la complexité spatiale et le caractère stable.

Principe de fonctionnement

On distingue les algorithmes procédant par comparaisons successives entre éléments, dits « tris par comparaisons », des algorithmes plus spécialisés faisant des hypothèses restrictives sur la structure des données à trier (par exemple, le tri par comptage, applicable uniquement si les données sont prises dans un ensemble borné connu à l'avance).

Les algorithmes de tri par comparaison lisent les entrées uniquement au moyen d'une fonction de comparaison binaire ou ternaire (lorsque le cas d'égalité est traité différemment). Il existe encore différents principes de fonctionnement au sein de cette classe : certains algorithmes de tri par comparaison procèdent par insertions successives, d'autres par fusions, d'autres encore par sélection.

En l'absence de précisions, on entend habituellement par « algorithme de tri » un algorithme de tri procédant par comparaisons.

Complexité algorithmique

  • La complexité temporelle ( en moyenne ou dans le pire des cas) mesure le nombre d'opérations élémentaires effectuées pour trier une collection d'éléments. C'est un critère majeur pour comparer les algorithmes de tri, puisque c'est une estimation directe du temps d'exécution de l'algorithme. Dans le cas des algorithmes de tri par comparaison, la complexité en temps est le plus souvent assimilable au nombre de comparaisons effectuées, la comparaison et l'échange éventuel de deux valeurs s'effectuant en temps constant.
  • La complexité spatiale ( en moyenne ou dans le pire des cas) représente, quant à elle, la quantité de mémoire dont va avoir besoin l'algorithme pour s'exécuter. Celle-ci peut dépendre, comme le temps d'exécution, de la taille de l'entrée. Il est fréquent que les complexités spatiales en moyenne et dans le pire des cas soient identiques. C'est souvent implicitement le cas lorsqu’une complexité est donnée sans indication supplémentaire.

La complexité en temps est souvent notée et exprimée comme une fonction du nombre d'éléments à trier à l'aide des notations de Landau et .

Certains algorithmes de tri simples ont une complexité en temps quadratique, i.e. , tandis que d'autres, plus élaborés, ont une complexité quasi-linéaire : .

La complexité temporelle en moyenne d’un algorithme basé sur une fonction de comparaison ne peut pas être meilleure que . Les tris qui ne demandent que comparaisons en moyenne sont par conséquent dits optimaux. Ce résultat constitue une borne inférieure asymptotique, mais on montre également que le nombre exact de comparaisons nécessaires est minoré par .

Pour certains types de données (entiers, chaînes de caractères de taille bornée), il existe cependant des algorithmes plus efficaces au niveau du temps d'exécution, comme le tri comptage ou le tri par base. Ces algorithmes n'utilisent pas la comparaison entre éléments (la borne n·log(n) ne s'applique donc pas pour eux) mais nécessitent des hypothèses sur les objets à trier. Par exemple, le tri comptage et le tri par base s'appliquent à des entiers que l'on sait appartenir à l'ensemble [1, m] avec comme hypothèse supplémentaire pour le tri par base que m soit une puissance de 2 (c’est-à-dire de la forme 2k).

Caractère en place

Un algorithme est dit en place s'il n'utilise qu'un nombre très limité de variables et qu’il modifie directement la structure qu’il est en train de trier. Ceci nécessite l’utilisation d'une structure de donnée adaptée (un tableau par exemple). Ce caractère peut être très important si on ne dispose pas d'une grande quantité de mémoire utilisable.

Remarquons toutefois qu'en général, on ne trie pas directement les données elles-mêmes, mais seulement des références (ou pointeurs) sur ces dernières.

Caractère stable

Un algorithme est dit stable s'il garde l'ordre relatif des éléments égaux pour la relation d'ordre considérée, c'est-à-dire l'ordre de ces éléments avant l'exécution de l'algorithme. Pour définir cette notion, il est nécessaire que la collection à trier soit ordonnée d'une certaine manière en entrée (ce qui est souvent implicitement le cas par la structure de données utilisée, par exemple lorsque l'entrée est fournie sous forme de liste ou de tableau).

Exemple :

Definissons la relation d'ordre définie sur les couples d'entiers par ssi , qui permet de trier deux couples selon leur première valeur.

Soit une liste de couples d'entiers que l'on souhaite trier selon la relation préalablement définie.

Puisque et sont égaux pour la relation , appeler un algorithme de tri avec en entrée peut mener à deux sorties différentes :

et sont toutes les deux triées selon , mais seule conserve l'ordre relatif. Dans , apparaît avant , d'où un algorithme de tri qui aurait pris en entrée et renvoyé en sortie serait instable.

Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stables, cependant cela peut être aux dépens de la rapidité et/ou peut nécessiter un espace mémoire supplémentaire.

Parmi les algorithmes listés plus bas, les tris étant stables sont : le tri à bulles, le tri par insertion et le tri fusion. Les autres algorithmes nécessitent mémoire supplémentaire pour stocker l'ordre initial des éléments.

Tri interne et externe

Un tri interne s'effectue entièrement en mémoire centrale tandis qu'un tri externe utilise des fichiers sur une mémoire de masse pour trier des volumes trop importants pour pouvoir tenir en mémoire centrale [1]. Certains types de tris, comme le tri fusion ou les tris par distribution, s'adaptent facilement à l'utilisation de mémoire externe. D'autres algorithmes, à l'inverse, accèdent aux données de telle sorte qu'ils ne se prêtent pas à cet usage car cela nécessiterait d'effectuer constamment des lectures/écritures entre les mémoires principale et externe.

Tri parallèle

Certains algorithmes permettent d'exploiter les capacités multitâches de la machine [2]. Notons également que certains algorithmes, notamment ceux qui fonctionnent par insertion, peuvent être lancés sans connaître l'intégralité des données à trier ; on peut alors trier et produire les données à trier en parallèle.

Other Languages
azərbaycanca: Sıralama alqoritmi
Bahasa Indonesia: Algoritma sorting
日本語: ソート
Lëtzebuergesch: Zortéieralgorithmus
олык марий: Ойыркалымаш
Nederlands: Sorteeralgoritme
norsk bokmål: Sorteringsalgoritme
polski: Sortowanie
中文: 排序算法