Tri dans un tableau

Intérêt des tableaux triés

Les tableaux sont une structure de données intuitive pour la gestion de collection d'éléments dont le nombre est connu (cf Les tableaux). Par leur grande simplicité d'implémentation, ils restent le choix principal des développeurs et ceci parfois à tord :
- les débutants les utilisent sans vergogne du fait de leur simplicité d'emploi. Souvent, ce choix est fait au détriment de structures comme les piles, les files ou les listes chaînées. Notons que les tableaux sont particulièrement contre-indiqués dans le cas d'une collection dont le nombre d'éléments est imprédictible et/ou s'il varie grandement au cours de l'exécution du programme.
- les développeurs plus à l'aise avec le langage de programmation préfèrent parfois les listes chaînées du fait de la souplesse qu'elles offrent à l'usage ou tout simplement parce qu'une liste chainée, "ça fait classe". Encore une fois, si le nombre d'éléments à gérer est connu, les tableaux triés sont tout indiqués.
 
Un tableau trié est un tableau dans lequel les éléments sont classés suivant un ordre logique,. Cela peut-être l'ordre croissant dans le cas de nombre, alphabétique pour des noms de famille ou toute autre méthode suivant le type de l'élément à considérer. La gestion et la recherche dans un tableau trié s'en trouve grandement facilité. Par exemple, le minimum ou le maximum du tableau est obtenu de manière triviale.

Recherche dans un tableau trié

Recherche dichotomique

Dans un tableau classique, la recherche est séquentielle, c'est à dire qu'elle nécessite de vérifier chaque élément un par un jusqu'à trouver le bon. Dans un tableau trié, il est possible de savoir si l'élément cherché est avant ou après un élément quelconque du tableau. Comme pour le jeu du plus ou moins, il est possible de s'aider de ces indices pour accélérer la recherche dans le tableau. C'est ce que l'on appelle la méthode dichotomique.
 
Explication de la dichotomie par un exemple concret :
Alice et Bob sont deux enfants voulant jouer ensemble à "devine le nombre auquel je pense". Alice pense à un chiffre entre 1 et 100 et Bob doit le trouver. A chaque essai, Alice lui indique plus ou moins en guise d'indice. Au premier essai, la seule certitude que possède Bob c'est que le nombre à deviner est dans l'intervalle [1,100]. La meilleure stratégie que peut mettre en place Bob à ce jeu est appelée méthode dichotomique. Elle consiste à se servir de ces indices pour réduire petit à petit l'intervalle des nombres possibles.
Bob: Bob commence, il annonce cinquante c'est à dire le milieu de son intervalle. Peu importe si le nombre est au-dessus ou en-dessous, il sait au moins que son intervalle sera deux fois plus petit!
Alice: moins
Bob: L'intervalle des possibilités est désormais [1;49]. A nouveau, il réduit de moitié cet intervalle et annonce vingt-cinq.
Alice: plus
Bob: Son intervalle est désormais [26;49], il propose donc trente-huit.
Alice: plus
Bob: Son intervalle est [38;49], il propose quarante-quatre.
Alice: moins
Bob: Le nombre à trouver est désormais entre [38 et 43], il propose: quarante.
Alice: plus
Bob: [41;43] Il propose: quarante deux.
Alice: juste!!
 
La méthode dichotomique permet la résolution de problèmes dont le domaine d'étude est réductible à un intervalle de possibilité. En réduisant de moitié cet intervalle à chaque essai, l'algorithme s'assure de manière statistique d'obtenir les meilleurs résultats. Rappelons que pour un ordinateur la chance n'est pas une bonne solution et que le hasard n'existe pas. Proposer des réponses "au hasard" n'est donc pas acceptable!
Pour un tableau à n éléments, il faudra au pire des cas diviser le tableau x fois en deux, avec x tel que n=2x. La complexité de la méthode dichotomique est alors dite en O(ln(n)) ce qui en fait un algorithme performant.
 
Un tableau ne contient pas forcément des chiffres, et il vous sera peut-être nécessaire de définir des méthodes permettant de déterminer ce qu'est être avant, après ou égal à un élément du tableau. Dans la suite, nous utiliserons trois fonctions renvoyant TRUE si element1 est respectivement avant, après ou égal à element2 :
boolean   IsAvant(element1, element2)
boolean   IsApres(element1, element2)
boolean   IsEgal(elemnt1, element2)

Algorithme de dichotomie en itératif

Primitive 'RechercheDichotomieIterative' en Pseudo-Code :

  1. Fonction RechercheDichotomiqueIterative(Tableau: tab, Element: valRecherche): entier
  2. deb:=0
  3. fin:=nombre d'élément -1
  4. TantQue deb tab[milieu]
  5. fin:=milieu+1
  6. FinSi
  7. FinTantQue
  8. retourner -1
  9. FinFonction

Algorithme de dichotomie en récursif

Primitive 'RechercheDichotomieRecursive' en Pseudo-Code :

  1. Fonction RechercheDichotomiqueRecursive(Tableau: tab,
  2. Element: valRecherche,
  3. deb: entier,
  4. fin: entier): entier
  5. milieu:=(fin-deb)/2
  6. Si tab[milieu]>ValCherche
  7. Rappeler la Fonction entre deb et milieu
  8. Sinon Si tab[milieu]

Méthodes de tri d'un tableau

Tri par sélection

Le tri par sélection -en anglais selection sort- est le plus naïf et intuitif des algorithmes de tri. Il consiste en effet à parcourir 'bêtement' le tableau à la recherche du plus petit élément. Lorsque celui-ci est trouvé, il est placé en première position. A nouveau, l'algorithme recherche le plus petit élément dans le reste du tableau et le place en seconde position. Cette procédure est répétée jusqu'à ce que le tableau soit trié. 
Pour trouver le plus petit élément du tableau lors de la première passe, la complexité exacte est O(n) [cf Recherche du minimum dans un tableau]. Lors de la seconde passe, la recherche est effectuée sur n-1 élément et la complexité est donc en O(n-1)=O(n). Chaque passe a pour complexité O(n). L'algorithme effectuant n passes, le tri par sélection s'effectue suivant une complexité exacte en O(n²) ce qui en fait un  algorithme peu performant.
 
Pour la suite, nous utiliserons les fonctions IsPlusGrand et IsPlusPetit et Echanger décrites comme suit. La fonction echanger permute simplement les éléments 1 et 2.
boolean   IsPlusGrand(element1, element2);
boolean   IsPlusPetit(element1, element2);
void      Echanger(element1, element2)
 
Primitive 'TriSelection' en Pseudo-Code :

  1. Fonction TriSelection(Tableau: tab):
  2. n := nombre d'éléments du tableau
  3. Pour i variant de 0 à n-1 :
  4. min:=i
  5. Pour j variant de i+1 à n:
  6. Si tab[j]

Tri à bulle

Le tri à bulle -en anglais Bubble sort- est un algorithme de tri légèrement supérieur en rapidité et en ingénieusité. Même s'il reste dans la catégorie des algorithmes "lents", le tri à bulle est pourtant souvent étudié dans les cours d'algorithmique.
Comme des bulles de champagne qui remonteraient à la surface du liquide, le tri à bulle fait remonter les grands éléments vers la fin du tableau. Cette migration le long du tableau s'effectue par permutation successive.
Initialisation: Un marqueur (en bleu) est placé en début de tableau,: il représente l'étape actuelle de travail. Un second marqueur (en rouge) est placé en fin de tableau: il représente l'endroit jusqu'où l'algorithme doit s'effectuer.
 
Schéma d'exécution d'un algorithme à bulle
1) Si la case sur laquelle se trouve le marqueur est plus petite que la suivante: se décaler de un. Sinon inverser la case avec la suivante. Ici: 1<9: se décaler de un.
 
2) 9>4: Inverser les deux cases.
 
3) 4<9: Se décaler de un.
 
4) 9>2: Inverser les deux cases.
 
5) 2<9: Se décaler de un.
 
6) 9>7: Inverser les deux cases.
 
7) 7<9: Il faudrait ici se décaler, mais dans ce cas, le marqueur bleu serait sur la même case que le marqueur rouge. Au lieu de cela, le marqueur bleu revient au début et le marqueur rouge se décale d'une case vers le début du tableau. Toutes les cases derrière le marqueur rouge sont garanties d'être triées, mais pas celles avant, d'où ....
 
8) L'algorithme reprend...
 
L'algorithme se termine soit lorsque les marqueurs bleu et rouge se retrouvent contigus ou alors lorsque le parcours entier du tableau par le marqueur bleu n'a pas donné lieu à une inversion. Dans ce cas, c'est que le tableau a fini d'être trié !
 
Considérons un tableau de n cases: dans le meilleur des cas, le tableau est déjà trié. Le marqueur bleu le parcourt donc une seule fois sans rien modifier, on dit que la complexité dans le meilleur des cas est en O(n). Dans le pire des cas, il faudra continuer l'algorithme jusqu'à ce que les marqueurs bleu et rouge se rejoignent, soit au bout de n parcours du tableau de n cases. La complexité dans ce pire cas est donc en O(n2).
 
Fonction 'TriABulle' en Pseudo-Code :

  1. Fonction TriABulle (Tableau: tab):
  2. ordonne := FAUX
  3. n := nbre element du tableau
  4. Pour i variant de 0 à n et si ordonne=FAUX:
  5. ordonne := VRAI
  6. Pour j variant de 1 à n-i
  7. Si tab[j-1] > tab[j]:
  8. Inverser tab[j-1] et tab[j]
  9. ordonne := FAUX
  10. FinSi
  11. FinPour
  12. FinPour
  13. FinFonction

Pour aller plus loin...

Tri rapide

Il existe de nombreux algorithmes de tri plus performant que ceux vu précédement. Parmi eux, le tri rapide -en anglais Quick Sort- est l'un des meilleurs en terme de temps d'exécution. Malheureusement sa compréhension est parfois plus difficile et l'espace mémoire requis pour effectuer cet algorithme est plus important.
 
La version "simple" du tri rapide a une complexité dans le meilleur des cas en O(n.log(n)) et une complexité au pire en O(n2), sachant que l'écart-type au meilleur cas est en O(n). Cela signifie que l'algorithme sera plus souvent bon que mauvais!
 
Améliorations possibles
Il existe des algorithmes de tri plus complexes comme l'algorithme IntroSort mais dont la complexité au pire cas reste en O(n.log(n)). Pour se faire, IntroSort utilise un compteur de récursion. Le tableau commence à être trié par un QuickSort. Au-delà d'une profondeur récursive de K.log(n) où K est une constante, les sous-tableaux sont triés par un algorithme de tri par tas (HeapSort) ou par SmoothSort.
 
Le principe de cet algorithme est de diviser successivement le tableau à trier en deux sous-parties. Celles-ci sont calculées suivant un élément appelé pivot: d'un côté seront les éléments dont la valeur est inférieure au pivot, de l'autre se retrouveront les éléments supérieurs au pivot. Par récursivité sur les sous-parties obtenues, la procédure va ainsi trier le tableau initial.
 
Schéma d'exécution de l'algorithme QuickSortDescription de l'algorithme :
Pour expliquer cet algorithme, nous prendrons appui sur le schéma ci-contre représentant le déroulement de l'exécution. Les éléments du tableau sont représentés par des batonnets de couleur dont la hauteur représente la valeur.
 
1) Le tableau n'est pas trié: un élément pivot marqué en rouge est choisit aléatoirement. C'est par rapport à cet élément que va s'effectuer la première passe. Deux marqueurs debut et fin respectivement en vert et violet sont initialisés en début et fin de tableau. (représentés sur le schéma par des petits triangles de couleur)
 
2) L'élément pivot est 'stocké' en fin de tableau. Pour cela une permutation est effectuée avec l'élément s'y trouvant. De plus, le marqueur debut avance dans le tableau jusqu'à trouver un élément plus grand que le pivot. De même, le marqueur fin parcourt le tableau dans l'autre sens à la recherche d'un élément inférieur au pivot.
 
3) Les deux éléments marqués sont inversés par permutation.
 
4) A nouveau, le marqueur debut continue le parcourt du tableau à la recherche d'un élément supérieur au pivot. D même, le marqueur fin se positionne le premier élément plus petit que le pivot qu'il trouve.
 
5) Les deux éléments marqués sont permutés et à nouveau les marqueurs continuent le parcours du tableau.
 
6) L'execution continue: des éléments respectivements plus grands et plus petits que le pivot sont marqués et sont échangés.
 
7) La première passe est terminée lorsque les deux marqueurs se rejoignent à un endroit quelconque du tableau. Le pivot est alors permuté avec l'élément 'doublement' marqué: la configuration est alors celle de l'étape 8.
 
8) La disposition crée par cette seconde passe est telle que tous les éléments situés avant le pivot lui sont inférieur tandis que les éléments après le pivot lui sont supérieurs. Le tableau est donc grossièrement pré-trié: d'un côté les plus petits que le pivot, de l'autre les plus grands.
 
Suite de l'algorithme: le tableau est scindé en deux moitiés: celle avant le pivot et celle après. Ces deux sous-tableaux sont à leur tour traités de la même manière: des marqueurs debut et fin sont initialisés et un pivot est choisi dans chacun des tableaux: la procédure peut reprendre.
Cette procédure est dite récursive: elle se rappelle elle-même. Lorsque les sous-tableaux obtenus seront de la taille d'un seul élément, la récursivité sera terminée et les sous-parties réassemblées en un tableau désormais trié.
 
Primitive 'TriRapide' en Pseudo-Code :

  1. Fonction TriRapide(Tableau: tab, entier: debut, entier: fin):
  2. gauche:=debut
  3. droite:=fin
  4.  
  5. pivot:= un élément du tableau au hasard
  6.  
  7. Echanger tab[droite] et pivot
  8.  
  9. TantQue gauche pas égal à droite
  10. TantQue tab[gauche] < pivot
  11. incrémenter gauche
  12. FinTantQue
  13. TantQue tab[droite] > pivot
  14. décrémenter droite
  15. FinTanQue
  16. Echanger tab[gauche] et tab[droite]
  17. FinTantQue
  18.  
  19. Echanger tab[droite] et pivot
  20.  
  21. TriRapide(tab, debut, gauche-1)
  22. TriRapide(tab, droite+1, fin)
  23. FinFonction

Votre note : Aucun(e) Moyenne : 3.8 (5 votes)