Objectifs
- Connaître les principaux algorithmes de tris d'entiers.
- Savoir dérouler les algorithmes à la main sur des petits tableaux
- Savoir produire le c/ de ces algorithmes
- CConnaître et savoir calculer la complexité des tris
Ce chapitre traite exclusivement des algorithmes classiques de tri. La théorie sera exposée et appliquée sur des tableaux d’entiers (les algorithmes sont généralisables à n’importe quel type et critère de classement).
On considère un tableau d’entier de taille N dont on veut trier les éléments de manière croissante. Une valeur peut être présente plusieurs fois dans le tableau. Ainsi:
| 11 | -2 | 1515 | 42 | 2048 | 28 | 11 | -78 |
devient, une fois trié:
| -78 | -2 | 11 | 11 | 28 | 42 | 1515 | 2048 |
On suppose l’existence d’une fonction echange / swap (voir chapitre précédent) qui permet de permuter dans un tableau t les cases d’indices i et j.
Le principe du tri sélection est le suivant:
[1, N-1] et on le permute avec la case d’indice 1.La procédure en C peut s’écrie comme:
// Rappel: on suppose l'existence de la fonction echange
void echange (int t[], int, int);
void tri_selection (int tab[], int N)
{
for (int ideb = 0; ideb < N - 1; ideb++)
{
int imin = ideb;
for (int i = ideb + 1; i < N; i++)
{
if (tab[i] < tab[imin]) imin = i;
}
echange (tab, ideb, imin);
}
}Du point de vue du coût de l’algorithme en terme de comparaisons, on constate que lorsque ideb vaut 0, il y a (N-1) comparaisons, lorsque ideb vaut 1 il y a (N-2) comparaisons… et lorsque ideb vaut (N-2) il y a 1 comparaison. Au final le coût est (N-1) + (N-2) + ... + 1 = n \times (n-1) / 2 qui lorsque N est très grand tend asymptotiquement vers O(N^2).
On peut également déterminer l’invariant de ce tri (i.e. quantité qui ne varie pas entre chaque tour de boucle, c’est utile pour les preuves d’algorithme). Pour le tri sélection, l’invariant est le suivant: à la fin du tour ideb, le sous tableau t[0..ideb] contient les ideb+1 plus petits éléments du tableau et ce, dans l’ordre croissant de leurs valeurs.
Le principe du tri intérieur est celui qu’on utilise pour trier des cartes à jouer:
Le c/ est le suivant:
void tri_insertion (int tab[], int N)
{
for (int i = 1; i < N; i++)
{
int current_element = tab[i];
int insertion_index = i;
while ((insertion_index >= 1) && (tab[insertion_index - 1] > current_element))
{
tab[insertion_index] = tab[insertion_index - 1];
insertion_index--;
}
tab[insertion_index] = current_element;
}
}La complexité de cette algorithme n’est pas aussi immédiate que précédemment. En effet dans la boucle while le nombre de comparaisons dépend de l’état initial du tableau (s’il est déjà trié ou non). En supposant que le tableau est trié, on remarque qu’il n’y a qu’une comparaison par tour de boucle, soit N-1 au total. A l’inverse si le tableau est trié par ordre décroissant, on aura 1 puis 2puis … puis N-2 comparaisons dans la boucle while. Ainsi la complexité est de O(N) dans le meilleur des cas et O(N^2) dans le pire des cas et en moyenne également.
L’invariant de ce tri est le suivant: au tour de boucle i, on insère l’élément t[i] dans le tableau t[0..i-1] déjà trié.
Le tri fusion utilise le principe de diviser pour régner. Pour cela il fonctionne de la manière suivante:
L’algorithme est un peu plus complexe que les deux précédents et se base sur des procédures auxiliaires. La procédure principale est la suivante:
void tri_fusion (int tab[], int N)
{
if (N > 1) fusion_recursive (tab, 0, N - 1);
}puis on détaille le coeur du tri (découpage en deux sous-tableaux)
void fusion_recursive (int tab[], int premier, int dernier)
{
if (premier < dernier)
{
int milieu = (premier + dernier) / 2;
fusion_recursive (tab, premier, milieu);
fusion_recursive (tab, milieu + 1, dernier);
fusion (tab, premier, milieu, dernier);
}
}puis la fusion de deux sous-tableaux
int fusion (int tab[], int premier1, int dernier1, int dernier2)
{
int premier2 = dernier1 + 1;
int c2 = premier2;
int c1 = premier1;
int fusion[dernier2 - premier1 + 1];
for (int i = 0; i < dernier2 - premier1 + 1; i++)
{
if ((c1 <= dernier1) && ((tab[c1] < tab[c2]) || (c2 > dernier2)))
{
fusion[i] = tab[c1];
c1++;
}
else
{
fusion[i] = tab[c2];
c2++;
}
}
for (int i = 0; i < dernier2 - premier1 + 1; i++)
{
tab[premier1 + i] = fusion[i];
}
}La complexité du tri-fusion se calcule comme suit: les comparaisons sont faites uniquement dans la fonction fusion (où il y a 3 comparaisons par tour de boucle). Pour trier le tableau complet:
3 \times n comparaisons.3 \times n comparaisons (cf il y a deux demi-tableaux).Au final il y a 3 \times n comparaisons par récursion avec en tout i récursions. i est tel que 2^i = N, soit i = ln_2(N). Ainsi la complexité asymptotique du tri-fusion est N \times ln_2(N).`
La section précédente a présenté 3 tris classiques, d’autres seront vus en TD et TP (tris à bulles et tri rapide).
Ci-desssous figure un récapitulatif des complexités des principaux algorithmes de tri:
| Algorithme | Meilleur | Moyenne | Pire |
| Tri à bulles | O(n) | O(n^2) | O(n^2) |
| Tri sélection | O(n^2) | O(n^2) | O(n^2) |
| Tri insertion | O(n) | O(n^2) | O(n^2) |
| Tri fusion | O(n x ln_2(n)) | O(n x ln_2(n)) | O(n x ln_2(n)) |
| Tri rapide | O(n x ln_2(n)) | O(n x ln_2(n)) | O(n^2) |
D’autres propriétés permettent de caractériser les algorithmes de tri:
O(n)).