Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Algorithmes de tri
Article mis en ligne le 18 février 2015
dernière modification le 22 février 2019

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
|||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

**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 :

  1. (define (dichot T v); T est un vecteur trié, v une valeur
  2.   (let* ((petit 0)
  3.          (grand (- (vector-length T) 1))
  4.          (pivot (quotient (+ grand petit) 2)))
  5.     (if (= v (vector-ref T grand))
  6.         grand
  7.         (if (= v (vector-ref T petit))
  8.             petit
  9.             (let loop ()
  10.               (if (and (not (= petit pivot))
  11.                        (not (= v (vector-ref T pivot))))
  12.                   (begin
  13.                     (if (< (vector-ref T pivot) v)
  14.                         (set! petit pivot)
  15.                         (set! grand pivot))
  16.                     (set! pivot (quotient (+ grand petit) 2))
  17.                     (loop))
  18.                   (if (not (= petit pivot)) pivot -1)))))))

Télécharger

*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 :

  1. (define (tri-insertv V)
  2.   (let ((L (vector-length V)))
  3.     (do ((i 1 (+ i 1)))
  4.         ((>= i L) V)
  5.       (let ((j 0))
  6.         (let loop ()
  7.           (if (and (< j i)
  8.                    (< (vector-ref V j)
  9.                       (vector-ref V i)))
  10.               (begin
  11.                 (set! j (+ j 1))
  12.                 (loop))))
  13.         (let ((k i)
  14.               (s (vector-ref V i)))
  15.           (let loop ()
  16.             (if (> k j)
  17.                 (begin
  18.                   (vector-set! V k
  19.                               (vector-ref V (- k 1)))
  20.                   (set! k (- k 1))
  21.                   (loop))))
  22.           (vector-set! V j s) ))) ))

Télécharger

**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 :

  1. (define (fusion L1 L2)
  2.    (if (null? L1) L2
  3.        (if (null? L2) L1
  4.            (if (< (car L1) (car L2))
  5.                (cons (car L1)
  6.                      (fusion (cdr L1) L2))
  7.                (cons (car L2)
  8.                      (fusion L1 (cdr L2)))))))

Télécharger

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 :

  1. (define (separe-et-applique L f g L1 L2)
  2.   (if (null? L)
  3.       (g (f L1) (f L2))
  4.       (separe-et-applique
  5.        (cdr L) f g L2 (cons (car L) L1))))

Télécharger

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 !

  1. (séparer-et-appliquer l trier fusion ’()())

et en somme :

  1. (define (tri-fusion L)
  2.   (if (or (null? L) (null? (cdr L)))
  3.       L
  4.       (separe-et-applique
  5.        L tri-fusion fusion '() '())))

Télécharger

**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.

$N(n) <= n-1+2\times N(n/2 +1)$
$N(n) <= n-1+2\times n/2\times 4 N(n/2+1/2+1)$
$N(n) <= n-1 + n + 4$

*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 :

  1. (define (tri-rapide v)
  2.    (define (tri-aux v imin imax)
  3.       (if (< imin imax)
  4.           (let ((q (partition v imin imax)))
  5.              (tri-aux v imin q)
  6.              (tri-aux v (+ q 1) imax)))
  7.       v)
  8.    (tri-aux v 0 (- (vector-length v) 1)))

Télécharger

  1.     (define (partition v imin imax)
  2.        (let ((x (vector-ref v imin)))
  3.           (let loop ()
  4.              (let loop1 ()
  5.                 (if (> (vector-ref v imax) x)
  6.                     (begin
  7.                        (set! imax (- imax 1))
  8.                        (loop1))))
  9.              (let loop2 ()
  10.                 (if (< (vector-ref v imin) x)
  11.                     (begin
  12.                        (set! imin (+ imin 1))
  13.                        (loop2))))
  14.              (if (< imin imax)
  15.                  (begin
  16.                     (swap v imin imax)
  17.                     (set! imin (+ imin 1))
  18.                     (set! imax (- imax 1))
  19.                     (loop))
  20.                  imax))))

Télécharger

  1. (define (swap v i j)
  2.   (let ((s (vector-ref v i)))
  3.     (vector-set! v i (vector-ref v j))
  4.     (vector-set! v j s) ))

Télécharger

*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 :

  1. (define (rmax v)
  2.    (let loop ((rmax 0)
  3.               (i 1))
  4.       (if (>= i (vector-length v))
  5.           rmax
  6.           (loop (if (> (vector-ref v i)
  7.                        (vector-ref v rmax))
  8.                     i
  9.                     rmax)
  10.                 (+ i 1)))))

Télécharger

  1. (define (rmin v)
  2.    (let loop ((rmin 0)
  3.               (i 1))
  4.       (if (>= i (vector-length v))
  5.           rmin
  6.           (loop (if (< (vector-ref v i)
  7.                        (vector-ref v rmin))
  8.                     i
  9.                     rmin)
  10.                 (+ i 1)))))

Télécharger

  1. (define (tri-lineaire v)
  2.    (let ((vmin (vector-ref v (rmin v)))
  3.          (vmax (vector-ref v (rmax v))))
  4.       (let ((b (make-vector (vector-length v)))
  5.             (c (make-vector (+ 1 (- vmax vmin)) 0)))
  6.          (do ((i 0 (+ i 1)))
  7.              ((>= i (vector-length v)) 'done)
  8.              (vector-set!
  9.               c
  10.               (- (vector-ref v i) vmin)
  11.               (+ 1 (vector-ref c (- (vector-ref v i) vmin)))))
  12.          (do ((i 1 (+ i 1)))
  13.              ((>= i (vector-length c)) 'done)
  14.              (vector-set! c i (+ (vector-ref c (- i 1))
  15.                                  (vector-ref c i))))
  16.          (do ((i 0 (+ i 1)))
  17.              ((>= i (vector-length v)) b)
  18.              (vector-set! b
  19.                           (- (vector-ref c (- (vector-ref v i)
  20.                                               vmin)) 1)
  21.                           (vector-ref v i))
  22.              (vector-set! c (- (vector-ref v i) vmin)
  23.                           (- (vector-ref c (- (vector-ref v i)
  24.                                               vmin))
  25.                              1))))))

Télécharger

* 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 :

  1. (define (arbre:creer taillemax)
  2.   (vector 'arbre 0 (make-vector (+ 1 taillemax))))
  3.  
  4. (define (arbre:taille T)
  5.   (vector-ref T 1))
  6.  
  7. (define (arbre:tableau T)
  8.   (vector-ref T 2))
  9.  
  10. (define (arbre:pere i)
  11.    (quotient i 2))
  12.  
  13. (define (arbre:fils-gauche i)
  14.    (* i 2))
  15.  
  16. (define (arbre:fils-droit i)
  17.    (+ 1 (* 2 i)))
  18.  
  19. (define (arbre:vide? T)
  20.    (zero? (arbre:taille T)))
  21.  
  22. (define (arbre:gauche-vide? T i)
  23.    (> (arbre:fils-gauche i)
  24.       (arbre:taille T)))
  25.  
  26. (define (arbre:droit-vide? T i)
  27.    (> (arbre:fils-droit i)
  28.       (arbre:taille T)))
  29.  
  30. (define (arbre:permute! T i j)
  31.   (let ((tmp (vector-ref T i)))
  32.     (vector-set! T i (vector-ref T j))
  33.     (vector-set! T j tmp)))

Télécharger

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 $h$ est donc $2^h$. La hauteur d’un arbre binaire à n feuilles est donc $log_{2}n$.

Le nombre de n\oeuds internes d’un arbre binaire complet de hauteur
$h$ est [2] :

$$ 1 + 2 + 2^2 + ... + 2^{h-1} = \sum_{i=0}^{h-1} 2^i = 2^h -1 $$

\noindent donc la complexité est : $log_{2}(taille(t))$.

**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

  1. (define (arbre:ajoute! T v)
  2.    (vector-set! T 1 (+ (arbre:taille T) 1))
  3.    (let ((i (arbre:taille T)))
  4.       (vector-set! (arbre:tableau T) i v)
  5.       (let boucle ((i i))
  6.          (if (and (> i 1)
  7.                   (> (vector-ref
  8.                       (arbre:tableau T) i)
  9.                      (vector-ref
  10.                       (arbre:tableau T)
  11.                       (arbre:pere i))))
  12.              (begin
  13.                 (arbre:permute!
  14.                  (arbre:tableau T) i (arbre:pere i))
  15.                 (boucle (arbre:pere i)))
  16.              T))))
  17.  
  18. (define (arbre:inserer-sommet! T v)
  19.    (vector-set! (arbre:tableau T) 1 v)
  20.    (let boucle ((i 1)
  21.                 (g 2)
  22.                 (d 3))
  23.           (if (or (and (<= g (arbre:taille T))
  24.                        (< (vector-ref
  25.                            (arbre:tableau T) i)
  26.                           (vector-ref
  27.                            (arbre:tableau T) g)))
  28.                   (and (<= d (arbre:taille T))
  29.                        (< (vector-ref
  30.                            (arbre:tableau T) i)
  31.                           (vector-ref
  32.                            (arbre:tableau T) d))))
  33.               (let ((m
  34.                      (if (> d (arbre:taille T))
  35.                          g
  36.                          (if (<
  37.                               (vector-ref
  38.                                (arbre:tableau T) g)
  39.                               (vector-ref
  40.                                (arbre:tableau T) d))
  41.                              d g))))
  42.                 (arbre:permute! (arbre:tableau T) i m)
  43.                 (boucle m
  44.                         (arbre:fils-gauche m)
  45.                         (arbre:fils-droit m))))))
  46.  
  47. (define (arbre:extraire T)
  48.    (let ((res (vector-ref (arbre:tableau T) 1))
  49.          (nouveau-sommet (vector-ref
  50.                           (arbre:tableau T)
  51.                           (arbre:taille T))))
  52.       (vector-set! T 1
  53.                    (- (arbre:taille T) 1))
  54.       (arbre:inserer-sommet! T nouveau-sommet)    
  55.       res))

Télécharger

  1. (define (trier-vecteur V)
  2.   (let* ((VL (vector-length V))
  3.          (T (arbre:creer VL)))
  4.      (do ((i 0 (+ i 1)))
  5.          ((>= i VL))
  6.          (arbre:ajoute! T (vector-ref V i)))
  7.      (do ((i (- VL 1) (- i 1)))
  8.          ((< i 0) V)
  9.          (vector-set! V i (arbre:extraire T)))))

Télécharger

  1. (define (n-min V n)
  2.    (let ((VL (vector-length V)))
  3.       (if (<= VL n)
  4.           (trier-vecteur V)
  5.           (let ((T (arbre:creer n)))
  6.              (do ((i 0 (+ i 1)))
  7.                  ((>= i n) T)
  8.                  (arbre:ajoute! T (vector-ref V i)))
  9.              (do ((i n (+ i 1)))
  10.                  ((>= i VL) T)
  11.                  (arbre:inserer-sommet! T (vector-ref V i)))
  12.              (let ((W (make-vector n)))
  13.                 (do ((i 0 (+ i 1)))
  14.                     ((>= i n) W)
  15.                     (vector-set! W
  16.                                  (- (- n 1) i)
  17.                                  (arbre:extraire T))))))))

Télécharger

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.