Les algorithmes de tri
Le tri est sans doute le problème fondamental de l’algorithmique
1. plus de 25% des CPU cycles sont dans les tri
2. le tri est fondamental à beaucoup d’autres problèmes, par exemple recherche binaire.
Ainsi donc, après le tri, beaucoup de problèmes deviennent faciles à résoudre. Par exemple :
1. Unicité d’éléments: après le tri tester les éléments adjacents
2. Une fois le tri fait, on peut déterminer le kème plus grand élément en O(1)
Les problème de tri discutés dans ce chapitre sont ceux où l’ensemble des données à trier se trouvent en mémoire centrale. Les problèmes de tri dont les données sont en mémoire secondaire ne sont pas discutés dans ce chapitre.
Le tri consiste à réarranger une permutation of n objets de telle manière
X1 ? X2 ? X3 ? ... ? Xn tri par ordre décroissant
X1 ? X2 ? X3 ? ... ? Xn tri par ordre croissant
Comment trier ? Il existe plusieurs solutions:
1. chercher le plus grand (le plus petit) élément
2. le mettre à la fin (au début)
Figure: tri par sélection Implémentation void selsort(Elem* array, int n)
{
for (int i=0; i<n-1; i++) { // Selectionner le ième element int lowindex = i; // mémoriser cet indice for (int j=n-1; j>i; j--) // trouver la plus petite valeur if (key(array[j]) < key(array[lowindex])) lowindex = j; // mettre à jour l’index swap(array, i, lowindex); échanger
}
}
Complexité : Le pire cas, le plus mauvais cas et le cas moyen sont pareils (pourquoi?)
Pour trouver le plus petit éléments, (n-1) itérations sont nécessaires, pour le 2ème plus petit élément, (n-2) itérations sont effectuées, .… Pour trouver le dernier plus petit élément, 0 itération sont effectuées. Le nombre d’itérations que l’algorithme effectue est donc:
Si par contre, nous prenons comme mesure d’évaluations le nombre de mouvement de données, alors l,algorithme en effectue n-1, car il y a exactement un échange par itération.
Dans ce cas, itérativement, nous insérons le prochain élément dans la partie qui est déjà triée précédemment. La partie de départ qui est triée est le premier élément.
En insérant un élément dans la partie triée, il se pourrait qu’on ait à déplacer plusieurs autres. void inssort(Elem* array, int n)
{
for (int i=1; i<n; i++) // insérer le ième element for (int j=i; (j>0) && (key(array[j])<key(array[j-1])); j--) swap(array, j, j-1);
}
Figure: tri par insertion
Complexité : Comme nous n’avons pas nécessairement à scanner toute la partie déjà triée, le pire cas, le meilleur cas et le cas moyen peuvent différer entre eux.
Meilleur cas: Chaque élément est inséré à la fin de la partie triée. Dans ce cas, nous n’avons à déplacer aucun élément. Comme nous avons à insérer (n-1) éléments, chacun générant seulement une comparaison, la complexité est en O(n).
Pire cas: Chaque élément est inséré au début de la partie trié. Dans ce cas, tous les éléments de la partie triée doivent être déplacés à chaque itération. La ième itération génère (i-1) comparaisons et échanges de valeurs:
Note: C’est le même nombre de comparaison avec le tri par sélection, mais effectue plus d’échanges de valeurs. Si les valeurs à échanger sont importantes, ce nombre peut ralentir cet algorithme d’une manière significative.
Cas moyen : Si on se donne une permutation aléatoire de nombre, la probabilité d’insérer l’élément à la kème position parmi les positions (0,1,2, …, i-1) est 1/i. Par conséquent, le nombre moyen de comparaisons à la ième itération est:
En sommant sur i, on obtient:
Tri par bulles.
La stratégie de cet algorithme est comme suit :
1. Parcourir le tableau en comparant deux à deux les éléments successifs, permuter s'ils ne sont pas dans l'ordre
2. Répéter tant que des permutation sont effectuées.
Exemple
void bubsort(Elem* array, int n) { // Bubble Sort for (int i=0; i<n-1; i++) // échanger for (int j=n-1; j>i; j--)
if (key(array[j]) < key(array[j-1])) swap(array, j, j-1);
}
5. Tri far fusion Cet algorithme divise en deux parties égales le tableau de données en question. Après que ces deux parties soient triées d’une manière récursive, elle sont fusionnées pour le tri de l’ensemble des données. Remarquez cette fusion doit tenir compte du fait que ces parties soient déjà triées.
Implantation void mergesort(Elem* array, Elem* temp, int left, int right)
{
int i, j, k, mid = (left+right)/2; if (left == right) return;
mergesort(array, temp, left, mid); // la première moitié mergesort(array, temp, mid+1, right);// Sort 2nd half
// l’opération de fusion. Premièrement, copier les deux moitiés dans temp.
for (i=left; i<=mid; i++) temp[i] = array[i]; for (j=1; j<=right-mid; j++) temp[right-j+1] = array[j+mid]; // fusionner les deux moités dans array for (i=left,j=right,k=left; k<=right; k++) if (key(temp[i]) < key(temp[j])) array[k] = temp[i++]; else array[k] = temp[j--]; }
Complexité:
La complexité de cet algorithme est donnée par la relation suivante:
n étant le nombre d’éléments dans le tableau.
Exercice: pourquoi les fonctions plancher et plafond comme paramètres dans T(.)?
Question : Peut-on parler des trois différentes complexités pour cet algorithme?
Dans le but de simplifier la résolution de l’équation 15.10, nous supposons que pour un entier k ? 0. En remplaçant O(n) par n, on obtient (en principe, on doit la remplacer par cn):
:
La complexité temporelle de tri par fusion est donc en O(nlog )n .
La stratégie de l’algorithme de tri rapide (quicksort) consiste, dans un premier temps, à diviser le tableau en deux parties séparées par un élément (appelé pivot) de telle manière que les éléments de la partie de gauche soient tous inférieurs ou égaux à cet élément et ceux de la partie de droite soient tous supérieurs à ce pivot (dans l’algorithme donné ci-dessus, la partie qui effectue cette tâche est appelée partition) . Ensuite , d’une manière récursive, ce procédé est itéré sur les deux parties ainsi crées. Notez que qu’au départ, le pivot est choisi dans la version de ci-dessus, comme le dernier élément du tableau.
Implantation void tri_rapide_bis(int tableau[],int debut,int fin){ if (debut<fin){
int pivot=partition(tableau,debut,fin); tri_rapide_bis(tableau,debut,pivot-1); tri_rapide_bis(tableau,pivot+1,fin);
} }
void tri_rapide(int tableau[],int n)
{
tri_rapide_bis(tableau,0,n-1);
}
void echanger(int tab[], int i, int j)
{
int memoire; memoire=tab[i]; tab[i]=tab[j]; tab[j]=memoire;
}
int partition(int tableau[], int deb, int fin){ int pivot = tableau[fin];
int i = debut ; j = fin; do{
do i++
while (tableau[i] < pivot)
do j--
while (tableau[j] > pivot) if (i < j)
echanger (tableau,i,j)
} while(i < j)
tableau[deb] = a[j]; tableau[j] = pivot; return(j) }
Choix du pivot : Le choix idéal serait que ça coupe le tableau exactement en deux parties égales. Mais cela n’est pas toujours possible. On peut prendre le premier élément. Mais il existe plusieurs autres stratégies!
Partitionnement : on parcourt le tableau de gauche à droite jusqu'à rencontrer un élément supérieur au pivot
on parcourt le tableau de droite à gauche jusqu'à rencontrer un élément inférieur au pivot
on échange ces deux éléments
et on recommence les parcours gauche-droite et droite-gauche jusqu'à a avoir :
il suffit alors de mettre le pivot à la frontière (par un échange)
À l’appel de QSORT (1,n), le pivot se place en position i. Ceci nous laisse avec un problème de tri de deux sous parties de taille i-1 et n-i.. L’algorithme de partition clairement a une complexité au plus de cn pour une constante c.
T(n) = T(i ?1) +T(n ?i) + cn
=1
T(1)
Voyons les trois cas possibles de complexité:
Le pivot est à chaque fois le plus petit élément. La relation de récurrence devient
T(n) = T(n – 1) + cn (pourquoi ?)
T(n -1) = T(n - 2) + c(n - 1)
T(n - 2) = T(n - 3) + c(n - 2) ... …….
T(2) = T(1) + c(2)
En ajoutant membre à membre, on obtient :
T(n) = O(n2 )
Cas favorable :
Dans le meilleur des cas, le pivot est, à chaque fois, situé au milieu de la parti à trier. T(n) = 2T(n/2) + cn
Ce développement s’arrête dès qu’on atteint T(1). Autrement dit, dès que
n/2k =1
n = 2k ? k = logn
Solution finale: T(n) = O(n log n) Question : déterminer la relation de récurrence exacte de la complexité dans ce cas de figure?
Nous savons que T(n) = T(i-1) + T(n - i) + cn (voir plus haut). Supposons que toutes les permutations des éléments du tableau soient équiprobables. Autrement dit, la probabilité que la case i soit choisie comme pivot est 1/n. Comme i peut varier entre 1 et n, alors on obtient facilement la récurrence suivante:
t(n) = cn+1?n t(i ?1) +t(n ?i)
ni=1
Comme ?=n t(i ?1) =?=n t(n ?i) , on obtient la relation: t(n) = cn + n2?i=n1 t(i) qui peut s’écrire aussi:
i 1 i 1
n
( = 2 +
qui est aussi vraie pour n+1. Autrement dit,
i=1
en soustrayant (1) de (2), on obtient:
(n +1)t(n +1) ? nt(n) = c(2n +1) + 2t(n +1) (n ?1)t(n +1) ? nt(n) = c(2n +1) t(nn+1) ? nt(n) = c(2n+?11)) = c(n2?1 ? 1n)
?1 n(n
Cette équation est aussi vraie pour n, n-1, n-2, …, 4
nt(?n)1 ? t(nn??21) = c(n?2 2 ? n1?1) t(nn??21) ? t(nn??32) = c(n2?3 ? n?1 2) t(nn??32) ? t(nn??43) = c(n?2 4 ? n1?3)
………
t(3) ? t(2) = c(?)
2 1
En additionnant membre à membre pour n, n-1,…., on obtient après simplifications:
nt(n) ? t(12) = c?? ?1 2 + n1?3 +...+1???+ c???1? n1?1???
?1 ?n
Or, on sait que :
log(n ? 2) <1+12 +...+ n?1 2 < log(n ?1)
on obtient donc :
t(n) < c(n ?1)???log(n ?1) +1?n1?1???+ t(2)
t(2) étant une constante, on obtient : t(n) = O(nlogn) .
La stratégie de cette méthode consiste à subdiviser à subdiviser la liste clés à trier en plusieurs sous-listes de telle manière que les éléments de chacune de ces listes sont à des positions à distance fixée, appelé incrément. Chacune de sous-listes est triée en utilisant l’algorithme de tri par insertion. Ensuite, un autre groupe de sous-liste est choisi avec un incrément plus petit que le précédent. On répète ce processus jusqu’à ce que l’incrément soit égal à 1.
Par exemple, supposons que le nombre n d’éléments à trier soit une puissance de 2. Si on choisit un incrément de départ de n/2, ensuite de n/4, … , jusqu’à 1, alors pour n =16, on aura 8 souslistes de 2 éléments, séparé de 8 positions dans le tableau; ensuite 4 sous-listes de 4 éléments séparés de 4 postions dans le tableau; ensuite 2 sous-listes de 8 éléments séparés 2 positions dans le tableau; ensuite une seule de 16 éléments. Par exemple :
void shellsort(Elem* array, int n)
{
for (int i=n/2; i>2; i/=2) // pour chaque incrément for (int j=0; j<i; j++) // trier chque sous-liste inssort2(&array[j], n-j, i); inssort2(array, n, 1);
}
// Version de tri par insertion avec des incréments qui varient
void inssort2(Elem* A, int n, int incr) { for (int i=incr; i<n; i+=incr) for (int j=i; (j>=incr) &&
(key(A[j])<key(A[j-incr])); j-=incr) swap(A, j, j-incr); }
La complexité de cet algorithme est de O(n3/ 2 )
