logo

Algorithme de tri



Algorithme de tri : encyclopédie mathématiques

wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.
Aller Ă  : navigation, rechercher

Un algorithme de tri est, en informatique ou en mathĂ©matiques, un 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’objets 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[modifier | modifier le code]

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 termes d'espace mĂ©moire utilisĂ©) et le caractĂšre stable.

Complexité algorithmique[modifier | modifier le code]

  • 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.
  • 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.

La complexitĂ©, gĂ©nĂ©ralement notĂ©e T, est exprimĂ©e en fonction du nombre n d'Ă©lĂ©ments Ă  l'aide des notations de Landau : O et Θ. Pour certains des algorithmes de tri les plus simples, T(n) = O(n2), pour les tris plus Ă©laborĂ©s, T(n) = 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.

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[modifier | modifier le code]

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[modifier | modifier le code]

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, 2)  (3, 3)  (5, 4)

que l'on trie par rapport Ă  leur premiĂšre coordonnĂ©e (la clĂ©), la seconde Ă©tant ici l'indice initial dans la suite, deux cas sont possibles, quand l’ordre relatif est respectĂ© et quand il ne l'est pas :

(3, 2)  (3, 3)  (4, 1)  (5, 4)   (ordre relatif maintenu)
(3, 3)  (3, 2)  (4, 1)  (5, 4)   (ordre relatif changé) 

Lorsque deux Ă©lĂ©ments sont Ă©gaux pour la relation d'ordre (c’est-Ă -dire qu'ils 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 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 O(n) mĂ©moire supplĂ©mentaire pour stocker l'ordre initial des Ă©lĂ©ments.

Tri interne et externe[modifier | modifier le code]

Un tri interne s'effectue entiÚrement en mémoire centrale alors 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[1].

Tri parallĂšle[modifier | modifier le code]

Certains algorithmes permettent d'exploiter les capacités multitùches de la machine[2].

Exemples d'algorithmes de tri[modifier | modifier le code]

Tris par comparaison[modifier | modifier le code]

Algorithmes lents[modifier | modifier le code]

Ces algorithmes sont lents pour plus de 20 éléments parce qu'ils sont en O(n2).

  • Tri Ă  bulles : Algorithme quadratique, T(n) = O(n2), 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(n2), 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(n2), 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[modifier | modifier le code]

  • Tri de Shell (shell sort) : AmĂ©lioration du tri par insertion, mais pas stable. ComplexitĂ© : au pire O(n \log^2 n) pour la sĂ©rie de pas 2^p3^q et O(n\sqrt{n}) pour la sĂ©rie de pas 2^k-1. On ne connaĂźt pas de sĂ©rie donnant O(n \log n).
  • Tri fusion (merge sort) : O(n \log n) en moyenne et dans le pire des cas, stable mais pas en place[3] ;
  • Tri rapide (quick sort) : O(n \log n) en moyenne, mais en O(n^2) (quadratique) au pire cas[4], en place mais pas stable
  • Introsort : AmĂ©lioration du tri rapide, qui permet une exĂ©cution en O(n \log n) dans tous les cas.
  • Tri par tas (heap sort) : O(n \log n) 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 O(n \log n), 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 ;
  • Tri par ABR : O(n \log n) en moyenne, O(n^2) dans le pire des cas. Ce tri est un des plus lents (parmi les tris rapides) et des plus gourmands en mĂ©moire Ă  cause de la structure d'arbre binaire Ă  manipuler. Il est possible de le rendre O(n \log n) dans tous les cas en maintenant un arbre Ă©quilibrĂ© (Arbre AVL).
  • 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 O(n \log n). 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).

Comparaison des algorithmes de tris en place[modifier | modifier le code]

Comparaisons tris sur petits tableaux.gif

Cette comparaison des algorithmes prend en compte le nombre d'accÚs en écriture dans le tableau ainsi que le nombre de comparaisons. 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.

Comparaisons tris sur tableaux moyens.gif

Lorsque l'on prend un nombre d'Ă©lĂ©ments moyen (entre 50 et 30 000), 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. Le smoothsort et le tri par tas changent de place. Enfin, la complexitĂ© du tri par insertion s'envole.

Comparaisons tris sur grands tableaux[modifier | modifier le code]

Avec un nombre d'Ă©lĂ©ments entre 30 000 et 6 000 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 lents pour ĂȘtre utilisĂ©s dans ce cas.

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[modifier | modifier le code]

  • 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 -- T(n) = O(n), part de l'hypothĂšse que les donnĂ©es Ă  trier sont rĂ©parties de maniĂšre uniforme sur un intervalle rĂ©el [a, b[.

Tris volumineux[modifier | modifier le code]

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[modifier | modifier le code]

Dans les débuts de l'informatique, lorsque le coût des mémoires de type disques ou tambours magnétiques était trÚs élevé, les algorithmes de tri pouvaient n'utiliser que la mémoire centrale et les dérouleurs de 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 de la fiabilité moyenne des équipements, on rencontrait donc fréquemment des salles machines avec 8 dérouleurs de bandes.

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Références[modifier | modifier le code]

  1. ↑ www.site.uottawa.ca/~kiringa/courses10/csi3530/ch13_extsort_csi3530-10.ppt
  2. ↑ http://www.umiacs.umd.edu/research/EXPAR/papers/3670.html
  3. ↑ On peut faire du tri fusion un tri en place et toujours en O(n \log n) mais l'algorithme effectue plus de copies et est plus compliquĂ© au niveau de la programmation
  4. ↑ 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.
wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.


maths - prof de maths - cours particuliers haut de pagehaut Retrouvez cette page sur ilemaths l'île des mathématiques
© Tom_Pascal & Océane 2014