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 :
Fonction RechercheDichotomiqueIterative(Tableau: tab, Element: valRecherche): entier
deb:=0
fin:=nombre d'élément -1
TantQue deb tab[milieu]
fin:=milieu+1
FinSi
FinTantQue
retourner -1
FinFonction
Implémentation en C de la primitive 'RechercheDichotomieIterative' (cliquer pour ouvrir)
int RechercheDichotomieIterative( Element* pTtab, Element valRecherche)
{
int milieu;
int deb= 0 ;
// détermination de la taille du tableau
int fin = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) - 1 ;;
// tant que l'intégralité du tableau n'a pas été parcouru
while ( deb
Algorithme de dichotomie en récursif
Primitive 'RechercheDichotomieRecursive' en Pseudo-Code :
Fonction RechercheDichotomiqueRecursive(Tableau: tab,
Element: valRecherche,
deb: entier,
fin: entier): entier
milieu:=(fin-deb)/2
Si tab[milieu]>ValCherche
Rappeler la Fonction entre deb et milieu
Sinon Si tab[milieu]
Implémentation en C de la primitive 'RechercheDichotomieRecursive' (cliquer pour ouvrir)
int RechercheDichotomiqueRecursive( Element* pTab,
Element valRecherche,
int deb,
int fin) {
// calcul de l'index de l'élément central
int milieu= ( fin- deb) / 2 ;
// Si l'élément est le bon...
if ( IsEgal( valRecherche, ptab[ milieu] ) )
{
// ... il est retourné
return milieu;
}
// Si l'élément cherché est "avant"...
if ( IsAvant( valRecherche, pTab[ milieu] ) )
{
// ...rappel de la fonction entre debut et milieu
RechercheDichotomiqueRecursive( pTab, valRecherche, deb, milieu- 1 ) ;
}
// Si l'élément cherché est "plus loin"...
if ( IsApres( valRecherche, pTab[ milieu] ) )
{
// ...rappel de la fonction entre milieu et fin
RechercheDichotomiqueRecursive( pTab, valRecherche, milieu+ 1 , fin) ;
}
// Ici: c'est que l'élément n'est pas dans le tableau
return - 1 ;
}
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 :
Fonction TriSelection(Tableau: tab):
n := nombre d'éléments du tableau
Pour i variant de 0 à n-1 :
min:=i
Pour j variant de i+1 à n:
Si tab[j]
Implémentation en C de la primitive 'TriSelection' (cliquer pour ouvrir)
void TriSelection( Element* pTab)
{
int i, j, min = 0 ;
// détermination de la taille du tableau
int iNbElements = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) ;
// pour chaque éléments du tableau
for ( i= 0 ; i
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.
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 :
Fonction TriABulle (Tableau: tab):
ordonne := FAUX
n := nbre element du tableau
Pour i variant de 0 à n et si ordonne=FAUX:
ordonne := VRAI
Pour j variant de 1 à n-i
Si tab[j-1] > tab[j]:
Inverser tab[j-1] et tab[j]
ordonne := FAUX
FinSi
FinPour
FinPour
FinFonction
Implémentation en C de la fonction 'TriABulle' (cliquer pour ouvrir)
void TriABulle( Element* pTab) {
int i, j, ordonne= 0 ;
// détermination de la taille du tableau
int iNbElements = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) ;
// au maximum n tour:
for ( i= 0 ; ( ( i
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 I ntroSort 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.
Description 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 :
Fonction TriRapide(Tableau: tab, entier: debut, entier: fin):
gauche:=debut
droite:=fin
pivot:= un élément du tableau au hasard
Echanger tab[droite] et pivot
TantQue gauche pas égal à droite
TantQue tab[gauche] < pivot
incrémenter gauche
FinTantQue
TantQue tab[droite] > pivot
décrémenter droite
FinTanQue
Echanger tab[gauche] et tab[droite]
FinTantQue
Echanger tab[droite] et pivot
TriRapide(tab, debut, gauche-1)
TriRapide(tab, droite+1, fin)
FinFonction
Implémentation en C de la primitive 'TriRapide' (cliquer pour ouvrir)
void TriRapide( int tableau[ ] , int debut, int fin)
{
// gauche et droite seront nos marqueurs pour l'algorithme
int gauche = debut;
int droite = fin;
// initialisation de rand
// choix aléatoire d'un pivot
int indicePivot
= rand ( ) % ( fin
- debut
) + debut
; // création du pivot
Element pivot = pTab[ indicePivot] ;
// Si le tableau est de longueur nulle, il n'y a rien à faire.
if ( debut >= fin)
return ;
// sauvegarde du pivot en fin de tableau
Echanger( pTab[ droite] , pivot) ;
// cette boucle représente une passe d'un étage de la récursivité
while ( gauche!= droite)
{
// Recherche du premier élément supérieur au pivot par la gauche
while ( IsAvant( pTab[ gauche] , pivot) )
{
gauche++;
}
// Recherche du premier élément inférieur au pivot par la droite
while ( IsApres( pTab[ droite] , pivot) )
{
droite--;
}
// échange des deux éléments
Echanger( pTab[ gauche] , pTab[ droite] ) ;
}
// replace le pivot dans le tableau
Echanger( pTab[ droite] , pivot) ;
// Tous les éléments inférieurs au pivot sont à gauche du margeur 'gauche'
// Tous les éléments supérieur au pivot sont à droite du margeur 'droite'
TriRapide( pTab, debut, gauche- 1 ) ;
TriRapide( pTab, droite+ 1 , fin) ;
// Fin du tri
return ;
}