Algorithme de tri 2932 30361610 2008-06-06T00:05:05Z Pixeltoo 12024 reformulation Un '''algorithme de tri''' est, en [[informatique]] ou en [[mathématiques]], un [[algorithmique|algorithme]] qui permet d'organiser une collection d'objets selon un ordre déterminé. Les objets à trier font donc partie d'un [[ensemble]] muni d'une [[relation d'ordre]] (de manière générale un ordre total). Les ordres les plus utilisés sont l’ordre numérique et l'[[ordre lexicographique]] (dictionnaire). Suivant la relation d'ordre considérée, une même collection d’objet peut donner lieu à divers arrangements, pourtant il est possible de définir un algorithme de tri indépendamment de la fonction d’ordre utilisée. Celui-ci ne fera qu'utiliser une certaine fonction d’ordre correspondant à une relation d’ordre qui doit permettre de comparer tout couple d'éléments de la collection. == 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. On distingue, tout d'abord, les algorithmes de tri d'application générale, procédant par comparaisons entre des paires d'éléments, et les algorithmes plus spécialisés faisant des hypothèses restrictives sur la structure des données entrées (par exemple, le tri par comptage, applicable uniquement si les données sont prises parmi un petit ensemble connu à l'avance). Si l'on ne précise rien, on entend habituellement par algorithme de tri un algorithme général de tri par comparaison. Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont : la [[complexité algorithmique]], les ressources nécessaires (notamment en terme d'espace mémoire utilisé) et le caractère stable. === Complexité algorithmique === * La [[complexité algorithmique]] temporelle ''dans le pire des cas'' permet de fixer une borne supérieure du nombre d'opérations qui seront nécessaires pour trier un ensemble de ''n'' éléments. On utilise pour symboliser cette complexité la [[Notations de Landau|notation de Landau]] : '''O'''. * La complexité algorithmique temporelle en moyenne : c’est le nombre d'opérations élémentaires effectuées ''en moyenne'' pour trier une collection d’éléments. Elle permet de comparer les algorithmes de tris et donne une bonne idée du temps d'exécution qui sera nécessaire à l’algorithme ; on arrive à l'estimer avec une précision assez importante. Toutefois, si les ensembles à trier ont une forme particulière et ne sont pas représentatifs des ''n '''!''' '' combinaisons possibles, alors les performances pourront être très inférieures ou très supérieures à la complexité « moyenne ». * La complexité algorithmique spatiale (en moyenne ou dans le pire des cas) représente, quant à elle, l’utilisation mémoire que va nécessiter l'algorithme. Celle-ci peut dépendre, comme le temps d'exécution, du nombre d'éléments à trier. Pour certains des algorithmes de tri les plus simples, T(''n'') = [[Notation O|O]](''n''<sup>2</sup>), pour les tris plus élaborés, T(''n'') = [[Notation O|O]](''n''·log(''n'')). On peut montrer que la complexité temporelle en moyenne et dans le pire des cas d’un algorithme basé sur une fonction de comparaison ne peut pas être meilleure que '''n·log(n)'''. Les tris qui ne demandent que ''n''·log(''n'') comparaisons en moyenne sont alors dits optimaux. {{boîte_déroulante_début|titre=Démonstration mathématique}} Le problème du tri consiste, étant donné une suite ''u'' = (''u<small>1</small>'', ''u<small>2</small>'', ..., ''u<small>n</small>'') d’éléments d’un ensemble totalement ordonné (par exemple <math>\mathbb{N}</math>), à déterminer une permutation σ de 1, ..., n telle que : ''y'' = (''u<small>σ(1)</small>'', ''u<small>σ(2)</small>'', ..., ''u<small>σ(n)</small>'') soit triée. Un algorithme de tri par comparaisons successives se modélise comme un [[arbre binaire]], chaque nœud de l'arbre correspondant à une comparaison entre deux éléments de l'ensemble. On compare deux éléments u<small>i</small> et u<small>j</small>, et en fonction du résultat, on passe à l'un des deux nœuds suivants, où l'on procède à une autre comparaison. Chaque feuille (nœud terminal) de l'arbre correspond à la suite totalement triée. L'algorithme doit être en mesure de fournir toutes les possibilités de permutation des termes de la suite, car il est équivalent de fournir la permutation σ que la suite triée ''y''. Le nombre de permutations de ''n'' éléments étant ''n '''!''' '' ([[factorielle]] n) le nombre de feuilles de l'arbre doit être au moins ''n '''!''' ''. Notons ''h'' la profondeur maximale de l'arbre (nous parlons bien d'un nombre d'étapes ''dans le pire des cas''). Le nombre maximal de feuilles dans un arbre binaire de profondeur maximale ''h'' est de <math>2^h</math>. Il vient donc : <math>2^h \geq n!</math> ; ainsi, asymptotiquement, <math>h \geq n \cdot \log_2(n)</math> (par utilisation de la [[formule de Stirling]]). Le fait qu'il existe des tris en <math>n \cdot \log_2(n)</math> montre d'autre part qu'il est possible d'avoir asymptotiquement <math>h \leq n \cdot \log_2(n)</math> d'où la notion de minimum. {{boîte_déroulante_fin}} 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 radix]]. 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 radix s'appliquent à des entiers que l'on sait appartenir à l'ensemble [1, ''m''] avec comme hypothèse supplémentaire pour le tri radix que ''m'' soit une puissance de 2 (c’est-à-dire de la forme 2<sup>k</sup>). === 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 [[pointeur (programmation)|pointeurs]]) sur ces dernières. === Caractère stable === Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre. Exemple, si on considère la suite d’éléments suivante : (4, 1) (3, 1) (3, 7) (5, 6) que l'on trie par rapport à leur première coordonnée (la clé), deux cas sont possibles, quand l’ordre relatif est respecté et quand il ne l'est pas : (3, 1) (3, 7) (4, 1) (5, 6) (ordre relatif maintenu) (3, 7) (3, 1) (4, 1) (5, 6) (ordre relatif changé) Lorsque deux éléments sont égaux ''pour la relation d'ordre'' (c’est-à-dire qu'il ont la même clé), l'algorithme de tri conserve l'ordre dans lequel ces deux éléments se trouvaient avant son exécution. Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stable, cependant cela peut être au 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 O(n) mémoire supplémentaire pour stocker l'ordre initial des éléments. == Exemples d'algorithmes de tri == === Tris par comparaison === ==== Algorithmes lents ==== Ces algorithmes sont lents pour plus de 20 éléments parce qu'ils sont en O(n<sup>2</sup>). * [[Tri à bulles]] : Algorithme quadratique, T(n) = O(n<sup>2</sup>), en moyenne et dans le pire des cas, stable et en place ; amusant mais pas efficace * [[Tri par sélection]] : Algorithme quadratique, T(n) = O(n<sup>2</sup>), en moyenne et dans le pire des cas, pas stable si tri sur place ; rapide lorsque l'on a moins de 7 éléments * [[Tri par insertion]] : Algorithme quadratique, T(n) = O(n<sup>2</sup>), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour des listes de moins de 15 éléments ; ==== Algorithmes plus rapides ==== * [[Tri de Shell]] (''shell sort'') : Amélioration du [[tri par insertion]], mais pas stable. Complexité: au pire <math>O(n \log^2 n)</math> pour la série de pas <math>2^p3^q </math> et <math>O(n\sqrt{n})</math> pour la série de pas <math>2^k-1</math>. On ne connaît pas de série donnant <math>O(n \log n)</math>. * [[Tri fusion]] (''merge sort'') : <math>O(n \log n)</math> en moyenne et dans le pire des cas, stable mais pas en place<ref>On peut faire du tri fusion un tri en place et toujours en <math>O(n \log n)</math> mais l'algorithme effectue plus de copies et est plus compliqué au niveau de la programmation</ref> ; * [[Tri rapide]] (''quick sort'') : <math>O(n \log n)</math> en moyenne, mais en <math>O(n^2)</math> (quadratique) au pire cas<ref>On peut rendre sa complexité algorithmique quasi-indépendante des données d'entrée en utilisant un pivot aléatoire ou en appliquant au tableau une [[permutation aléatoire]] avant de le trier.</ref>, en place mais pas stable * [[Introsort]] : Amélioration du [[tri rapide]], qui permet une exécution en <math>O(n \log n)</math> dans tous les cas. * [[Tri par tas]] (''heap sort'') : <math>O(n \log n)</math> en moyenne et dans le pire des cas, en place mais pas stable. Toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de <math>O(n \log n)</math>, il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide ; * [[Smoothsort]] : tri inspiré du [[tri par tas]] en utilisant un arbre non inversé, ce tri est très rapide pour les ensembles déjà presque triés, sinon, il est en <math>O(n \log n)</math>. Tri en place mais pas stable Note : on peut facilement obtenir la stabilité d'un tri si l'on associe à chaque élément sa position initiale. Pour cela, on peut créer un deuxième tableau de même taille pour stocker l'ordre initial (on renonce alors au caractère ''en place'' du tri). <references/> ==== Comparaison des algorithmes de tris en place ==== [[Image:Comparaisons tris sur petits tableaux.gif]] Cette comparaison des algorithmes prend en compte le nombre d'accès en écriture dans le tableaux ainsi que le nombre de comparaison. Par exemple pour un tri simple avec 2 éléments, il y a une comparaison, et si échange il y a, deux accès en écriture. Les données à trier sont choisies aléatoirement et le temps moyen est calculé. Avec ces critères, les algorithmes de tris en place les plus rapides sur des tableaux de moins de 40 éléments sont le [[tri de Shell]] et le [[tri rapide]] (quicksort). Si le [[tri par insertion]] est parmi les premiers pour moins de 10 éléments, sa complexité augmente rapidement au-delà. Le [[tri par tas]] est clairement le plus lent. Le [[smoothsort]] obtient une position intermédiaire. Notes : *le [[tri de Shell]] du test utilise les pas optimisés (1, 4, 10, 23...) *pour le [[tri rapide]], l'utilisation de l'optimisation de Sedgewick ou de l'[[introsort]] ne change que très peu la vitesse moyenne sur les petits tableaux. [[Image:Comparaisons tris sur tableaux moyens.gif]] Lorsque l'on prend un nombre d'éléments moyen (entre 50 et 30000), le tri en place le plus rapide est le [[tri rapide]]. La variante Sedgesort est légèrement plus rapide si l'on choisit bien la taille des petites listes, triées à la fin (ici au plus 8). Ensuite vient le [[tri de Shell]] qui n'est plus le plus rapide. Notons aussi que le [[smoothsort]] et le [[tri par tas]] échangent de place. Enfin, la complexité du [[tri par insertion]] s'envole... ===== Comparaisons tris sur grands tableaux ===== Avec un nombre d'éléments entre 30&nbsp;000 et 6&nbsp;000&nbsp;000 d'éléments, les résultats sont sensiblement les mêmes que pour les tableaux moyens. L'optimisation de Sedgewick est légèrement plus intéressante même si le gain reste marginal. D'autre part, le [[tri par insertion]], de même que le [[tri à bulles]] et le [[tri par sélection]], sont beaucoup trop lent pour être utilisés dans ce cas. {| class="wikitable" |+ ''Rapport entre complexité mesurée et complexité optimale'' ! ! Sedgesort ! Quicksort simple ! Shellsort ! Heapsort ! Smoothsort |----- ! Rapport | 1,8 | 1,9 | 2,8 | 3 | 4,1 |} === 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 ; * [[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 -- <math>T(n) = O(n)</math>, part de l'hypothèse que les données à trier sont réparties de manière uniforme sur l'ensemble <math>[0, 1[</math>. === Tris volumineux === 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 : * On découpe le volume de données à trier en sous-ensembles de taille inférieure à la mémoire rapide disponible, * On trie chaque sous-ensemble en mémoire centrale pour former des "monotonies" (sous-ensembles triés). * On interclasse ces monotonies. ====Tris bande==== Dans les débuts de l'informatique, lorsque le coût des mémoires de type [[Disque dur|disques]] ou [[Tambour (mémoire)|tambours magnétiques]] était très élévé, les algorithmes de tri pouvaient n'utiliser que la mémoire centrale et les dérouleurs de [[Bande magnétique|bandes magnétiques]]. En l'absence de disque, il fallait au moins 4 dérouleurs de bandes pour pratiquer un tel tri. Avec 4 dérouleurs (b1, b2, b3, b4), les opérations étaient les suivantes : * (1) montage (manuel) du fichier à trier sur le dérouleur b1, et de bandes de manœuvre sur b2, b3, b4 ; * (2) lecture de b1 par paquets successifs qui sont triés en mémoire, pour générer des monotonies qui sont écrites en alternance sur les dérouleurs b3 et b4 ; * (3) sur le dérouleur b1, démontage de la bande contenant le fichier initial pour le remplacer par une bande de manœuvre ; * (4) fusion (interclassement) des bandes b3 et b4 pour générer en alternance sur b1 et b2 des monotonies dont le volume est doublé ; * (5) fusion de b1 et b2 sur b3 b4, et itération de (4) et (5) jusqu'à ce que les monotonies atteignent 50 % du volume à trier ; * fusion finale pour générer le résultat. En pratique, compte tenu le la fiabilité moyenne des équipements, on rencontrait donc fréquemment des salles machines avec 8 dérouleurs de bandes. == Liens externes == * {{fr}} [http://www.herve.name/algo.php Mémoire de synthèse sur les algorithmes de tri] * {{fr}} [http://www.dailly.info/algorithmes-de-tri/index.php Dossier sur les algorithmes de tri et leur complexité (et implémentation en divers langages)] * {{fr}} [http://thomas.baudel.name/Visualisation/VisuTri/index.fr.html Illustration dynamique de plusieurs tris (nécessite Java)] * {{fr}} [http://interstices.info/tri Sur le site Interstices, document sur les algorithmes de tri avec une applet Java] {{Algorithme de tri}} {{Portail informatique}} [[Catégorie:Algorithme de tri| ]] [[ar:خوارزميات الترتيب]] [[ca:Algorisme d'ordenació]] [[cs:Řadicí algoritmus]] [[da:Sorteringsalgoritme]] [[de:Sortierverfahren]] [[en:Sorting algorithm]] [[es:Algoritmo de ordenamiento]] [[fa:الگوریتم مرتب‌سازی]] [[fi:Lajittelualgoritmi]] [[he:מיון (מדעי המחשב)]] [[hu:Rendezés (programozás)]] [[is:Röðunarreiknirit]] [[it:Algoritmo di ordinamento]] [[ja:ソート]] [[ko:정렬 알고리즘]] [[lb:Zortéieralgorithmus]] [[lt:Rikiavimo algoritmas]] [[nl:Sorteeralgoritme]] [[no:Sorteringsalgoritme]] [[pl:Sortowanie]] [[pt:Algoritmo de ordenação]] [[ru:Алгоритм сортировки]] [[sv:Sorteringsalgoritm]] [[th:ขั้นตอนวิธีการเรียงลำดับ]] [[tr:Sıralama algoritması]] [[uk:Алгоритми сортування]] [[vi:Thuật toán sắp xếp]] [[zh:排序算法]]