Les tris

Les tris

1 Le problème du tri

Le problème du tri est défini de la manière suivante :
Entrée : une séquence de n nombres (a1, a2, ..., an)
Sortie : un réarrangement de la séquence d'entrée (a'1, a'2, ..., a'n)
telle que a'1 ? a'2 ? ... ? a'n
La séquence d'entrée est en général un tableau à n éléments bien qu'elle
puisse être également représenté différemment, par exemple sous la forme
d'une liste chaînée. Dans la suite pour simplifier la représentation des
algorithmes on considérera que la séquence placée en entrée est un tableau
.

2 Tri par insertion


Le principe

Le tri par insertion est en général le tri qu'on utilise pour trier une
poignée de cartes par exemple à la belote ou au tarot. On commence avec une
main vide et les cartes face contre table. On retire ensuite une à une les
cartes du paquet en les insérant à leur "bonne" place. Pour trouver cette
bonne place, on la compare avec chacune des cartes déjà présentes dans la
main, de droit à gauche.

L'algorithme

On considère que tab est un tableau d'entiers pour simplifier mais le
raisonnement reste valable quelque soit le type des éléments contenus dans
le tableau tant qu'une comparaison entre les éléments est possible.
En entrée de notre procédure on a un tableau tab. Les nombres du tableau
sont triés sur place : ils sont réorganisés à l'intérieur du tableau avec
au plus un nombre constant d'entre eux stockés dans de variables
intermédiaires à "l'extérieur" du tableau à un instant donné. Le tableau
d'entrée tab contient la séquence triée à la fin de la méthode.

Tri_Par_Insertion (Tableau tab)
{
entier i, j; /* indice pour mes boucles */
entier clé; /* variable temporaire pour contenir l'élément
courant que je cherche à repositionner */


pour j = 1 à longueur(tab)
{
clé = tab[j]
/* Insertion de tab[j] dans la séquence triée
tab[0 ... j-1] */
i = j - 1;
tant que ((i > -1) et (tab[i] > clé))
{
/* On parcours le sous-tableau tab[0 ... j-1] de la
droite vers la gauche tant que tab[i] est plus
grand que tab[j] ou que l'on a pas encore atteint
la 1ère case du tableau */
tab[i + 1] = tab[i];
i = i - 1;
}
/* A la sortie de cette boucle tant que i+1 est l'indice auquel
nous devons ranger notre élément. */
tab[i+1] = clé;
/* On peut remarquer que le tri du tableau ce fait "sur place" :
il y a un nombre constant d'éléments sortie du tableau à un moment
donné. */
}








Le tri par insertion utilise une approche incrémentale : on trie le sous
tableau tab[0 ... j-1] puis on insère l'élément unique tab[j] au bon
emplacement, on a ainsi le tableau trié A[0 ... j].
Si on note n la taille du tableau, on effectuera n fois la boucle "pour
j = 1 ...". A l'intérieur de cette boucle pour, dans le pire cas on aura à
effectuer (n-1) fois la boucle "tant que ((i > -1) ...". Intuitivement on
s'aperçoit que dans le pire cas on effectuera K * n * (n-1) opérations
élémentaires, K étant ici une constante. On dira que cette algorithme est
en O(n2) dans le pire cas. Cette notation et l'idée derrière cela est
identique à l'idée de fonction équivalente en mathématique quand le
paramètre de la fonction tant vers une certaine valeur.

3 Tri par selection


Le principe

On parcourt le tableau pour rechercher le plus petit élément que l'on
permute alors avec le premier élément. Le même traitement est effectué avec
le tableau ayant le premier élément en moins. Cette opération est répétée
jusqu'à ce que tous les éléments soient classées.

L'algorithme

On considère toujours que tab est un tableau d'entiers. Tant que le
tableau n'est pas entièrement trié, on détermine le sous-tableau non encore
trié. Tant que ce sous-tableau n'a pas été entièrement parcouru on
recherche dedans le plus petit élément et quand on l'a trouvé on le permute
avec le premier élément du sous-tableau non encore trié


Tri_Par_Selection(Tableau tab)
{
entier i, j, lePlusPetit, indiceDuPlusPetit;


i = 0;
tant que ( i < (longueur(tab)-1))
{
/* Les 2 lignes suivantes permettent de traiter le cas où le
premier élément est le plus petit */
lePlusPetit = tab[i];
indiceDuPlusPetit = i;
j = i+1;
/* Boucle pour rechercher le plus petit élément */
tant que (j < longueur(tab))
{
si (tab[j] < lePlusPetit)
{
lePlusPetit = tab[j];
indiceDuPlusPetit = j;
}
j = j + 1;
}
/* permutations des 2 éléments */
tab[indiceDuPlusPetit] = tab[i];
tab[i] = lePlusPetit;
i = i + 1;
}
}
Encore une fois on s'aperçoit intuitivement que l'on passera dans la
boucle "tant que (i < (longueur(tab) - 1))" (n-1) fois si n est la longueur
du tableau tab et que l'on passera (n-1) fois dans la deuxième boucle "tant
que". Comme dans le cas précédent, notre algorithme est en O(n2)

4


5


6


7 Tri par propagation ou tri à bulle


Le principe

Le tri est réalisé en propageant par permutations successives le plus
grand élément du tableau à la fin de celui-ci (comme les bulles qui
remontent à la surface d'un liquide, le plus grand élément gagne de proche
en proche l'extrémité droite du tableau). Ce principe est répété pour
chacun des éléments

L'algorithme



Tri_Par_Propagation (Tableau tab)
{
entier nbrEltATrier, i, j, stop, temp ;
nbrEltATrier = longueur(tab);
tant que (nbrEltATrier > 0)
{
i = 1;
stop = 0;
tant que (i < nbrEltATrier)
{
si (tab(i) > tab(i+1))
{
temp = tab(i);
tab(i) = tab(i+1);
tab(i+1) = temp;
stop = i;
}
i = i + 1;
}
nbrEltATrier = stop;
}
}


De même que pour les 2 algorithmes précédents, on comprend intuitivement
que dans le pire cas nous allons avoir un algorithme qui sera en O(n2)
Il existe des méthodes de tris plus efficaces que les 3 présentées ici
que nous aurons l'occasion d'étudier par la suite.

8 9


10 Le tri rapide


Introduction

Le tri rapide est fondé sur une approche "diviser pour régner". Le tri
rapide nous fait introduire les notions de récurrence et de récursivité.
Une méthode sera dite récursive si dans le corps de cette méthode elle
s'appelle elle-même. En mathématique, vous avez déjà dû manipuler des
suites qui étaient définies de manières récursives. Vous aviez Un qui était
fonction de Un-1 et on vous donnez la valeur de U0. Ici c'est pareil.
Considérons le calcul de la factorielle : factorielle(n) = n *
factorielle(n-1) et factorielle(0) = 1. Nous avons vu dans le cours une
méthode qui calculer la factorielle de manière itérative. Voici
l'algorithme d'une fonction qui calcule la factorielle de manière itérative


Entier Factorielle(Entier n)
{
si (n == 0)
{
retourne (1);
}
sinon
{
retourne (n*Factorielle(n-1));
}


On voit dans cet exemple que pour calculer la valeur de la factorielle
pour n, on la calcule d'abord pour n-1, et ainsi de suite. On s'arrête
grâce à la condition initiale, à savoir que Factorielle(0) vaut 1. Nous
allons voir que le tri rapide est un algorithme récursif.

Description

Comme énoncé dans la section précédente le tri rapide est fondé sur une
approche "diviser pour régner" que l'on peut décomposer en 3 étapes. On
considère que nous avons un tableau Tab de taille n. On notera un "sous-
tableau" de Tab, Tab[p...r], p étant l'indice du début du sous-tableau et r
l'indice de la fin du sous tableau. On remarquera qu'un sous-tableau est un
tableau et que Tab[0...n-1] est le sous-tableau représentant le tableau Tab
en entier.
1. Diviser : le sous-tableau Tab[p...r] est partitionné( i.e. réarrangé)
en 2 sous-tableaux non vides Tab[p..q] et Tab[q+1..r] de telle sorte
que chaque élément du tableau Tab[p..q] soit inférieur ou égal à
chaque élément de A[q+1...r]. l'indice q est calculé pendant la
procédure de partitionnement.
2. Régner : Les 2 sous-tableaux A[p..q] et A[q+1..r] sont triés par des
appels récursifs à la méthoide principale de tri-rapide.
3. Combiner : le tri rapide effectue "le tri sur place" (cf. la section
2.2 sur le tri par insertion). Cela implique qu'il n'y a aucun travail
supplémentaire pour les fusionner : le sous-tableau Tab[p..r] tout
entier est maintenant trié.


Le tri rapide va comporter 2 méthodes triRapide(Tableau tab, Entier p,
Entier r) et partitionner(Tableau tab, Entier p, Entier r), qui renvoie un
entier. L'entier renvoyé par partitionner est l'indice que l'on recherche
dans l'étape "Diviser". L'appel initial sur le tableau tab sera
triRapide(tab, 0, tab.length). Voici les algorithmes des 2 méthodes.


triRapide(Tableau tab, Entier p, Entier r)
{
Entier q;
si (p < r)
{
q = partitionner(tab, p, r);
triRapide(tab, p, q);
triRapide(tab, q+1, r);
}
}








Entier partitionner(Tableau tab, Entier p, Entier r)
{
Entier eltPivot; /* on