par Laurent Bloch, William Saurin
Un autre article de ce site propose d’autres algorithmes de tri, notamment sur les vecteurs.
Recherche dichotomique
Aurait-on-pu aller plus vite dans la recherche d’un élément dans une liste ?
Comment cherche-t-on un mot dans un dictionnaire ? on regarde les mots de la page qui est au milieu du dictionnaire et on se demande si celui que l’on cherche est dans la page, s’il plus grand que le dernier ou s’il est plus petit que le premier. S’il est dans la page : c’est trouvé, s’il est plus petit on recommence sur la moitié inférieure du dictionnaire et s’il est plus grand on recommence sur la moitié supérieure.
Algorithme dichotomique
Exemple
Rechercher 176 dans le tableau suivant :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 17 | 43 | 89 | 100 | 113 | 156 | 176 | 231 | 248 | 301 |
petit | pivot | grand | ||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 17 | 43 | 89 | 100 | 113 | 156 | 176 | 231 | 248 | 301 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 17 | 43 | 89 | 100 | 113 | 156 | 176 | 231 | 248 | 301 |
Combien de fois fait on le test “grand != petit et t[pivot] _ != v”
En fait à chaque étape on coupe l’espace de recherche (le tableau en 2) . On cesse de faire des tests lorsque l’espace de recherche contient au plus un ou deux éléments.
étape | 1 | 2 | 3 | 4 | ... | n |
taille du tableau | t | t/2 | t/4 | t/8 | ... | t/2n-1 |
A l’étape n (où on s’arrête) on a une taille 2<= t/2n−1 et donc
2n <= t et donc n <= log2t
Selon l’algorithme le nombre de test est :
En Scheme :
Tri par insertion
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
100 | 10 | 8 | 56 | 78 | 4 | 67 | 34 |
Nous nous proposons de trier un tableau V représenté par un vecteur de longueur Vlen
.
L’idée est simple : à un certain moment de l’algorithme la région qui va de 0 à k − 1 dans le tableau est déjà triée. Il suffit pour avoir une séquence triée de 0 à k d’insérer V[k] dans cette séquence. Insérer c’est trouver le premier élément dans la séquence de 0 à k−1 tel que cet élément soit plus grand que V[k], on décale alors tous les éléments y compris celui là d’un rang vers le haut et on insère l’élément V[k] dans le trou.
Il y a un piège : si on décale tous les éléments vers la droite, à la fin du décalage V[k] doit contenir V[k-1]. Il faut donc avoir sauvegardé V[k] avant le décalage : il nous faut une variable auxiliaire.
On peut observer que la séquence qui va de 0 à 0 dans un tableau est toujours triée.
Pour une étape donnée il faut faire :
trouver où insérer ;
sauvegarder V[j] ;
décaler ;
insérer V[j] dans le trou.
Pour trouver la place de l’insertion, nous procéderons par dichotomie pour éviter des performances trop mauvaises.
En somme :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 10 | 56 | 100 | 78 | 4 | 67 | 34 |
__ |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 10 | 56 | 100 | 78 | 4 | 67 | 34 |
__ |
puis :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 10 | 56 | 100 | 78 | 4 | 67 | 34 |
__ |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 10 | 56 | 100 | 4 | 67 | 34 | |
__ |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 10 | 56 | 78 | 100 | 4 | 67 | 34 |
Pseudo-code
Traduisons en Scheme :
Complexité
Le nombre d’opérations de comparaisons d’éléments de tableau de cet algorithme est en O(n2) en effet il y a n−1 étape à chacune d’entre elles on fait au plus le nombre de comparaison correspondant au nombre d’éléments de la séquence trié de l’étape, pour l’étape 1 1, pour l’étape 2 2, et ainsi de suite soit 1+2+3+...+n−1 si n est la taille du tableau et donc au plus (n−1)n/2 comparaisons à chaque étape il y a au plus i décalages si i est le numéro de l’étape et donc de la même façon (n−1)n/2 décalage élémentaires.
Tri fusion
L’idée est la suivante. Supposons que nous ayons deux ensembles de valeurs triées (dans une liste par exemple) pour fabriquer une liste triée à partir des deux listes triées il suffit de se dire que si la première liste est vide le résultat est la seconde, si la seconde est vide, le résultat est la première si aucune des deux n’est vide il suffit de prendre la tête de la liste qui est la plus petite et de la concaténer à la liste résultant de la fusion du reste de cette liste et de l’autre liste. En Scheme :
Ainsi on voit que pour trier une liste il suffit de la séparer en deux sous listes, de trier chacune de ces listes et de les fusionner. Sauf si la liste est vide au départ, dans ce cas elle est déjà triée !
Séparer une liste en deux sous-listes et appliquer une fonction f à chacun de ces sous-listes et enfin appliquer une fonction g à ces deux sous-listes peut s’écrire :
Pour trier par fusion la liste l il suffirait d’appeler séparer-et-appliquer
à a
avec comme fonction g fusion et comme fonction f une fonction qui trie une liste !
et en somme :
Combien de cons
?
À la première étape on fera pas plus de cons
qu’il n’y a d’éléments dans la liste de départ -1. Mais on aura aussi dû faire le nombre de cons
nécessaire à trier les deux sous-listes qui n’ont chacune pas plus que n/2 +1 éléments.
Tri rapide (Quicksort)
L’algorithme Quicksort a été publié par C.A.R. Hoare [1] en 1962.
Une autre façon de faire consiste à choisir un élément du tableau à trier, nous appellerons cet élément le pivot, puis a s’assurer que tous les éléments plus petit ou égaux au pivot sont au début du tableau et les éléments plus grand ou égaux à la fin. Il y a de la sorte deux région créés dont tous les éléments de la première sont plus petits ou égaux à ceux de la seconde. De la sorte le tableau est partiellement trié, il suffit alors de trier la partie basse et la partie haute.
On peut écrire qu’à chaque étape on fera :
- choisir le pivot ;
- créer deux régions une au début qui ne contienne aucun élément plus grand que pivot, une à la fin qui ne contienne aucun élément plus petit que pivot ; soit q la position fin de la première région :
-
- trier les éléments du début à q,
- trier les éléments de q +1 à dernier élément ;
Supposons qu’il s’agisse de trier les éléments du tableau entre les positions imin et imax (comprises), on pourrait dire que le pivot est imin puis on examinerait en descendant tous les éléments du tableau de imax vers imin jusqu’à en avoir trouvé un plus petit ou égal au pivot appelons jmax cette position. On peut ensuite parcourir le tableau de imin jusqu’à ce qu’on ait trouvé un élément plus grand ou égal que le pivot ; appelons jmin cette position. Si jmin est inférieur à jmax alors on échange les valeurs en jmin et jmax on incrémente jmin et on décrémente jmax puis on recommence à balayer vers le bas (pour jmax) et vers le haut (pour jmin). Si jmin n’est pas inférieur à jmax alors il est clair que jmax est le haut de la région de valeur inférieures au pivot.
On peut alors trier entre imin et jmax et entre jmax +1 et imax.
avec l’algorithme suivant pour partition :
En Scheme :
Tri linéaire
Il s’agit de trier un tableau V mais nous savons dans quel intervalle sont présentes les valeurs de V.
On peut alors créer un tableau C dont les indices vont de valeur la plus petite de V (vmin) à valeur la plus grande de V (vmax). C est initialisé à 0.
On parcourt V et pour chaque valeur de V[i] on fait C[V[i]] ← C[V[i]] +1. A la fin dans c[v[i]] on a le nombre de fois que la valeur C[V[i]] est présente dans V. On peut alors calculer les sommes cumulées de C[vmin] ... C[i] on a maintenant en C[i] le nombre de valeurs de V qui sont inférieures ou égales à i. On parcourt une fois V et pour chaque V[i] rencontré on écrit sa valeur en C[V[i]] dans un tableau B et on fait C[V[i]] ← C[V[i]]−1.
À la fin B est une version triée de A.
En Scheme :
Tas
Un tas est un objet qui peut être vu comme un arbre binaire complet : à part peut-être un seul de ses sous arbres tous ont soit un ou deux fils qui sont des arbres-vides soit deux fils qui ne sont pas des arbres vides. Tous les sous-arbres non vides se présentent sur deux niveaux au plus. Enfin lorsqu’on examine deux sous arbres vides dont l’un est à gauche de l’aure, le sous arbre de gauche est toujours à une profondeur supérieure ou égale à celui de droite. La valeur d’un sous arbre est toujours plus élevée que les valeurs contenues dans ses sous arbres droit et gauche.
Pour mémoire, un arbre est une structure de données définie de la façon (récursive) suivante :
– un arbre est soit l’arbre vide soit un nœud ;
– un nœud a des fils qui sont des arbres ;
– si tous les fils d’un nœud sont l’arbre vide on dit que ce nœud est une feuille ;
– outre des fils, chaque nœud comporte une valeur ;
– si chaque nœud a n fils l’arbre est dit n-aire.
Un arbre peut en outre avoir une racine, qui est un nœud situé en haut quand on le dessine, contrairement aux arbres des forêts. Les nœuds qui ne sont pas des feuilles sont parfois appelés « nœuds intérieurs ».
Représentation d’un tas : on peut le représenter par un tableau (de longueur l) et par une valeur qui représente le nombre de sous-arbres non vides du tas. Les valeurs du tas seront stockées dans les cellules 1 à taille du tas (attention à la taille maximum du tas qui doit être plus petite d’un que la taille du tableau). De la sorte la valeur du fils gauche de l’arbre dont la valeur sera en position i du tableau sera stockée en 2i et le fils droit en 2i+1, de la même manière le père d’un nœud en position i sera en Entier(i/2).
De le même façon :
et fils droit :
Comment ajouter un élément à un tas ? On augmente la taille du tas de 1, on place le nouvel élément dans la case d’indice \texttttaille dans le tableau et on le laisse remonter (en échangeant sa valeur avec son père) tant qu’il a un père (on n’est pas à la racine) dont la valeur est inférieure à celle du nouvel élément :
Complexité de l’algorithme :
Combien de feuilles pour un arbre binaire complet ? Chaque nœud intérieur a deux fils, le nombre de feuilles à la profondeur est donc . La hauteur d’un arbre binaire à n feuilles est donc .
Le nombre de n\oeuds internes d’un arbre binaire complet de hauteur
est [2] :
\noindent donc la complexité est : .
Représentation graphique d’un tas :
Cette illusration, comme les suivantes, est empruntée à W. Lang de l’université de Flensburg en Allemagne, qui propose un excellent site sur le sujet.
Représentation par un tableau du tas de la figure précédente.
Insérer un nouvel élément dans le tas à la place du sommet :
Peut-on extraire l’élément maximum du tas et conserver au tas sa structure ? Il suffit de prendre l’élément en position 1 (que l’on extrait), de placer en position 1 l’élément qui est en position taille du tas puis de le faire descendre tant qu’il n’est pas en bas et que l’un de ses fils plus grand que lui après avoir réduit d’un la taille du tas. Il descend de la sorte en étant échangé avec son fil de valeur la plus élevée.
On peut alors utiliser ces deux algorithmes pour trier un tableau.
En voici une illustration :
(a) Extraire l’élement maximum
(b) Détruire la dernière feuille et réécrire son étiquette à la racine
(c) Permuter le sommet avec son plus grand descendant direct
(d) Permuter l’étiquette avec l’étiquette maximum de ses descendants directs
(e) Tas restauré
Tri par tas
On peut utiliser ces algorithmes pour déterminer quels sont les k plus petits éléments d’un flux de données. On commencerait par construire un tas avec les k premiers éléments du flux. À partir de l’élément k+1 du flux on pourrait pour chacun des éléments suivants tester s’il est plus petit que l’élément au sommet du tas et si c’est le cas l’insérer au sommet du tas.
Exercice : Ecrire l’algorithme décrit informellement ci-dessus en supposant qu’une fonction fct rend des valeurs successives ou bien qu’elle rend -1 comme dernière valeur.