Algorithmes de tri

Auteurs : William Saurin, Laurent Bloch

#Sommaire-

<!—TOC section Recherche dichotomique.—>

Recherche dichotomique

<!—TOC subsection Aurait-on-pu aller plus vite dans la recherche d'un élément dans une liste?—>

Aurait-on-pu aller plus vite dans la recherche d'un élément dans une liste ?

<!—SEC END —>

Comment recherche-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 qu'on recherche 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.
<!—TOC subsection Algorithme dichotomique—>

Algorithme dichotomique

<!—SEC END —> Nom de l'algorithme : dichot Donnée d'entrée : vecteur trié t et valeur v Résultat : numéro dans la liste petit <- 0 grand <- longueur de t -1 pivot <- Entier(grand/ 2) si v = t[grand] alors retourner grand sinon si v =t[petit] alors retourner petit sinon tant que pivot != petit et t[pivot] != v faire si t[pivot] < v alors petit <- pivot sinon grand <- pivot finsi pivot <- Entier((grand - petit) / 2) fin tant que si pivot != petit alors retourner pivot sinon retourner -1 fin si
<!—TOC subsection Exemple—>

Exemple

<!—SEC END —>

Rechercher 176 dans le tableau suivant :

0 1 2 3 4 5 67 8 9 10 11

1 17 43 89 100 113 156 176 231 248 301

petit pivot grand

0 1 2 3 4 5 67 8 9 10 11

1 17 43 89 100 113 156 176 231 248 301

petit pivot grand

0 1 2 3 4 5 67 8 9 10 11

1 17 43 89 100 113 156 176 231 248 301

<!—TOC subsection Combien de fois fait on le test “grand != petit et t[pivot] != v”—>

Combien de fois fait on le test “grand != petit et t[pivot] != v”

<!—SEC END —>

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/2ⁿ⁻¹

A l'étape n (où on s'arrête) on a une taille 2<= t/2ⁿ⁻¹ et donc
2ⁿ<= t et donc n <= log₂t
Selon l'algorithme le nombre de test est :
<!—TOC subsection En Scheme :—>

En Scheme :

<!—SEC END —> (define (dichot t v) ; t est un vecteur triée v une valeur (let* ((petit 0) (grand (- (vector-length t) 1)) (pivot (quotient (+ grand petit) 2))) (if (= v (vector-ref t grand)) grand (if (= v (vector-ref t petit)) petit (let loop () (if (and (not (= petit pivot)) (not (= v (vector-ref t pivot)))) (begin (if (< (vector-ref t pivot) v) (set ! petit pivot) (set ! grand pivot)) (set ! pivot (quotient (+ grand petit) 2)) (loop)) (if (not (= petit pivot)) pivot -1)))))))
<!—TOC section Tri par insertion—>

Tri par insertion

Un tableau A :

0 1 2 3 4 5 6 7

100 10 8 56 78 4 67 34

L’idée est simple : on va se dire qu’à un certain moment de l’algorithme la région qui va de 0 à j dans le tableau est déjà triée. Il suffit donc pour avoir une séquence triée de 0 à j + 1 d’insérer A[j+1] dans cette séquence. Insérer c’est donc trouver le premier élément dans la séquence de 0 à j tel que cet élément est plus grand que A[j+1] on décale alors tous les éléments y compris celui là d’un vers le haut et on insère l’élément A[j+1] dans le trou. Il y a deux pièges :

• Si on décale tous les éléments vers la droite, à la fin du décalage A[j+1] doit contenir A[j]. Il faut donc avoir sauvegardé A[j+1] avant le décalage : il nous faut une variable auxiliaire.
• si A[j+1] est plus petit que A[0] il ne faut pas essayer de le comparer à A[−1] !

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 :

1. trouver où insérer ;
2. sauvegarder A[j+1] ;
3. décaler ;
4. insérer A[j] dans le trou.

En somme :

01234567

810561007846734

__

01234567

810561007846734

^__

puis

01234567

81056100 46734

^__

78

01234567

81056 10046734

^__

01234567

810567810046734

<!—TOC subsection Pseudo-code—>

<!—SEC ANCHOR —>Pseudo-code

<!—SEC END —>

Nom de l'algorithme : tri-insertion Donnée : un tableau V Résultat : V est trié pour j allant de 1 à (longueur de V) -1 faire i <- j - 1 tant que i > 0 et V[i] < V[j] faire i <- i - 1 fait si i > 0 alors rotation-droite (V, i + 1 , j - 1) sinon rotation-droite (V, i , j - 1) fait retourner V Nom de l'algorithme : rotation-droite Données : un tableau V, i, j s <- V[j+1] k <- j tant que k > i faire V[k+1] <- V[k] k <- k - 1 fait V[i] <- s

<!—TOC subsection Traduisons en Scheme :—>

<!—SEC ANCHOR —>Traduisons en Scheme :

<!—SEC END —>(define (rotation-droite V i j) (let ((Vlen (vector-length V))) (if (>= j (- Vlen 1)) 'impossible (let ((tmp (vector-ref V (+ j 1)))) (do ((k j (- k 1))) ((< k i) (vector-set ! V i tmp)) (vector-set ! V (+ k 1) (vector-ref V k)))))))

(define (tri-insert V) (let ((Vlen (vector-length V))) (do ((j 1 (+ j 1))) ((> j (- Vlen 1)) V) (let loop ((i (- j 1))) (cond ((> (vector-ref V j) (vector-ref V i)) (rotation-droite V (+ i 1) (- j 1))) ((zero ? i) ;; cas particulier (rotation-droite V i (- j 1))) (else (loop (- i 1)))) ) )))

<!—TOC subsection Complexité—>

Complexité

<!—SEC END —>

Le nombre d'opérations de comparaisons d'éléments de tableau de cet algorithme est en O(n²) 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écalage 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.
<!—TOC section Tri fusion—>

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 :

(define (fusion l1 l2) (if (null ? l1) l2 (if (null ? l2) l1 (if (< (car l1) (car l2)) (cons (car l1) (fusion (cdr l1) l2)) (cons (car l2) (fusion l1 (cdr l2)))))))
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 :
(define (separe-et-applique l f g l1 l2) (if (null ? l) (g (f l1) (f l2)) (separe-et-applique (cdr l) f g l2 (cons (car l) l1))))
Pour trier par fusion la liste l il suffirait d'appeler separe-et-applique à a avec comme fonction g fusion et comme fonction f une fonction qui trie une liste !
(separe-et-applique l trier fusion '() '())
et en somme :
(define (fusion l1 l2) (if (null ? l1) l2 (if (null ? l2) l1 (if (< (car l1) (car l2)) (cons (car l1) (fusion (cdr l1) l2)) (cons (car l2) (fusion l1 (cdr l2))))))) (define (separe-et-applique l f g l1 l2) (if (null ? l) (g (f l1) (f l2)) (separe-et-applique (cdr l) f g l2 (cons (car l) l1)))) (define (tri-fusion l) (if (or (null ? l) (null ? (cdr l))) l (separe-et-applique l tri-fusion fusion '() '())))
<!—TOC subsection Combien de cons ?—>

Combien de cons ?

<!—SEC END —>

A la première étape on fera pas plus de cons qu'il y a d'éléments dans la liste de départ -1. Mais on aura aussi du faire le nombre de cons nécessaire à trier les deux sous-liste qui ont chacune pas plus que n/2 +1 éléments.

N(n) <= n−1 + 2 * (N(n/2 +1))

N(n) <= n−1 + 2 * n/2 * 4(N(n/2 +1 / 2 +1))

N(n) <= n−1 + n + 4

Faire un arbre !!!
<!—TOC section Tri rapide (Quicksort)—>

Tri rapide

L'algorithme Quicksort a été publié par C.A.R. Hoare¹ en 1962.
Une autre façon de faire consiste à choisir un élément du tableau à trier, nous appellerons cet élément le pivot, puis à s'assurer que tous les éléments plus petits 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éées 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 :

1. choisir le pivot ;
2. 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 a 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 aupivot 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.
Nom de l'algorithme : tri-rapide Donnée d'entrée : un vecteur v, imin et imax les bornes dans lesquelles trier si imin < imax alors q <- partition(v, imin, imax) tri-rapide(v, imin, q) tri-rapide(v, q+1, imax) finsi
avec l'algorithme suivant pour partition :
Nom de l'algorithme : partition Données d'entrée : un vecteur v, imin et imax les bornes dans lesquelles partitionner x <- v[imin] tant que vrai faire tant que v[imax] > x faire imax <- imax -1 fait tant que v[imin] < x faire imin <- imin + 1 fait si imin < imax alors echanger v[imax] et v[ iman] imax <- imax - 1 imin <- imin + 1 sinon retourner imax finsi fait
<!—TOC subsection En Scheme :—>

En Scheme :

<!—SEC END —> (define (tri-rapide V) (define (tri-aux V imin imax) (if (< imin imax) (let ((q (partition V imin imax))) (tri-aux V imin q) (tri-aux V (+ q 1) imax))) V) (tri-aux V 0 (- (vector-length V) 1))) (define (partition V imin imax) (let ((x (vector-ref V imin))) (let boucle () (do ((i imax (- i 1))) ((<= (vector-ref V imax) x)) (set! imax i)) (do ((i imin (+ i 1))) ((>= (vector-ref V imin) x)) (set! imin i)) (if (< imin imax) (begin (permute V imax imin) (set! imax (- imax 1)) (set! imin (+ imin 1)) (boucle)) imax)))) (define (permute V i j) (let ((tmp (vector-ref V i))) (vector-set! V i (vector-ref V j)) (vector-set! V j tmp)))

En voici une version compilée et générique, qui reçoit en paramètre le prédicat qui définit la relation d'ordre à appliquer pour le tri, et qui en infère aussi le type des éléments à trier, nombres ou chaînes de caractères :

(module tri-rapide-2 (main def-tri)) ;; ./bin/make-tri-rapide "string<=?" 5 8 2 0 78 0 1 12 42 2 4 ;; #(0 0 1 12 2 2 4 42 5 78 8) ;; ./bin/make-tri-rapide ">=" 5 8 2 0 78 0 1 12 42 2 4 ;; #(78 42 12 8 5 4 2 2 1 0 0) (define (def-tri Args) (let* ((nom-predicat (cadr Args)) (le-tri (make-tri-rapide (eval (string->symbol nom-predicat)))) (le-vecteur (list->vector (cond ((string=? (substring nom-predicat 0 1) "s") (cddr Args)) ;; on trie des chaînes de caractères (else ;; on trie des nombres (map string->number (cddr Args))))))) (print (le-tri le-vecteur)))) ;; (define mon-tri (make-tri-rapide (eval (string->symbol "string<=?")))) ;; (mon-tri '#("Alice" "Julot" "Bernard" "Élodie")) ;; #(Alice Bernard Julot Élodie) (define (make-tri-rapide predicat) (define (tri-aux V imin imax) (if (< imin imax) (let ((q (partition V imin imax))) (tri-aux V imin q) (tri-aux V (+ q 1) imax))) V) (define (tri-rapide V) (tri-aux V 0 (- (vector-length V) 1) )) (define (permute V i j) (let ((tmp (vector-ref V i))) (vector-set! V i (vector-ref V j)) (vector-set! V j tmp))) (define (partition V imin imax) (let ((x (vector-ref V imin))) (let boucle () (do ((i imax (- i 1))) ((predicat (vector-ref V i) x) (set! imax i))) (do ((i imin (+ i 1))) ((predicat x (vector-ref V i) ) (set! imin i))) (if (< imin imax) (begin (permute V imax imin) (set! imax (- imax 1)) (set! imin (+ imin 1)) (boucle)) imax)))) tri-rapide) ;; make-tri-rapide renvoie une procédure, ;; qui est le programme de tri voulu

<!—TOC section Tri linéaire—>

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.

Nom de l'algorithme : tri-linéaire Données d'entrée : v un vecteur Donnée en sortie : b un vecteur qui contient toutes les valeurs de v triées Créer un vecteur c de longueur valeur maximum de v - valeur minimum de v + 1 initialisé à 0 pour toutes ses valeurs. pour i allant de 0 à longueur de v -1 faire c[v[i] - vmin] <- c[v[i] - vmin] + 1 fait pour i allant de 1 à longueur de c -1 faire c[i] <- c[i] + c[i-1] fait créer un vecteur b de longueur longueur de c pour i allant de longueur de v -1 à 0 faire b[c[v[i] -vmin] - 1] <- v[i] c[v[i]-vmin] <- c[v[i]-vmin] - 1 fait retourner b
Combien d'opérations ?
<!—TOC subsection En Scheme :—>

En Scheme :

<!—SEC END —> (define (rmax v) (let loop ((rmax 0) (i 1)) (if (>= i (vector-length v)) rmax (loop (if (> (vector-ref v i) (vector-ref v rmax)) i rmax) (+ i 1))))) (define (rmin v) (let loop ((rmin 0) (i 1)) (if (>= i (vector-length v)) rmin (loop (if (< (vector-ref v i) (vector-ref v rmin)) i rmin) (+ i 1)))))
(define (tri-lineaire v) (let ((vmin (vector-ref v (rmin v))) (vmax (vector-ref v (rmax v)))) (let ((b (make-vector (vector-length v))) (c (make-vector (+ 1 (- vmax vmin)) 0))) (do ((i 0 (+ i 1))) ((>= i (vector-length v)) 'done) (vector-set ! c (- (vector-ref v i) vmin) (+ 1 (vector-ref c (- (vector-ref v i) vmin))))) (do ((i 1 (+ i 1))) ((>= i (vector-length c)) 'done) (vector-set ! c i (+ (vector-ref c (- i 1)) (vector-ref c i)))) (do ((i 0 (+ i 1))) ((>= i (vector-length v)) b) (vector-set ! b (- (vector-ref c (- (vector-ref v i) vmin)) 1) (vector-ref v i)) (vector-set ! c (- (vector-ref v i) vmin) (- (vector-ref c (- (vector-ref v i) vmin)) 1))))))

Tas et tri par 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.
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 etre 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 noeud en position i sera en Entier(i/2).

Nom de l'algo : père Donnée : i Résultat : la position du père de i retourner Entier(i/2)
De le même façon :
Nom de l'algo : fils-gauche Entrée : i Résultat : la position du fils gauche de i retourner 2 * i
et fils droit :
Nom de l'algo : fils-droit Donnée : i Résultat : la position du fils droit de i retourner (2 * i) + 1
(define (tas:creer taillemax) (vector 'tas 0 (make-vector (+ 1 taillemax)))) (define (tas:taille T) (vector-ref T 1)) (define (tas:tableau T) (vector-ref T 2)) (define (tas:pere i) (quotient i 2)) (define (tas:fils-gauche i) (* i 2)) (define (tas:fils-droit i) (+ 1 (* 2 i))) (define (tas:permute ! T i j) (let ((tmp (vector-ref T i))) (vector-set ! T i (vector-ref T j)) (vector-set ! T j tmp)))
Problème : comment ajouter un élément à un tas. On augmente la taille du tas de 1, on positionne le nouvel élément à l'indice taille dans le tableau et on le laisse remonter (en échangeant sa valeur avec son père) tant que son père existe (on n'est pas à la racine) ou que celui-ci à une valeur inférieure à la valeur du noeud :
Nom de l'algo : augmenter-tas Données : T, un tas, et v, une valeur Résultat : le tas comportant la nouvelle valeur taille de T <- taille de T + 1 i <- taille de T T [i] <- v tant que i > 1 et T [i] > T[pere(i)] faire échanger T [i] et T[pere(i)] i <- pere (i) fait
La complexité de l'algorithme ? log₂(taille(t)).
On peut envisager d'insérer un nouvel élément dans le tas à la place du sommet de la façon suivante :
Nom de l'algo : insérer-tas Données : v, T une valeur et un tas. Résultat : T le tas T[1]<-v i<-1 tant que (fils-gauche(i) < taille de T et T[fils-gauche(i)] > T[i]) ou (fils-droit[i] < taille de T et T[fils-droit(i)]> T[i]) faire si fils-droit(i) > taille de T ou T[fils-droit(i)] <= T[fils-gauche(i)] alors echanger T[fils-gauche(i)] et T[i] sinon echanger T[fils-droit(i)] et T[i] finsi retourner T

---

Exemple :

Figure 1 : Tas = 10 sommets

---

(Cette figure et la suivante sont empruntées à H. W. Lang de l'université de Flensburg en Allemagne, qui propose un excellent site sur le sujet : http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm)

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.

Nom de l'algo : extraire-tas Données : T un tas Résultat : v le plus grand élément de T v<- tableau de T[1] taille de T <- taille de T -1 inserer-tas(T[taille de T + 1], T) retourner v
On peut alors utiliser ces deux algorithmes pour trier un tableau.

---

(a) (b) (c)

Figure 2 : Extraire l'élément le plus grand et restaurer la structure de tas

(d) (e)

---

Nom de l'algo : Tri-par-tas Données : V un tableau Résultat : V trié. t <- creer un tas contenant un tableau de taille longueur de V + 1 taille de t = 0 pour i allant de 0 à longueur(V) - 1 faire augmenter-tas(t, V[i]) fait pour i allant de 0 à longueur de V - 1 faire V[longueur(V) - 1 - i] <- extraire-tas(t) fait retourner V

---

Figure 3 : Représentation par un tableau du tas de la figure 1

(define (tas:ajoute ! T v) (vector-set ! T 1 (+ (tas:taille T) 1)) (let ((i (tas:taille T))) (vector-set ! (tas:tableau T) i v) (let boucle ((i i)) (if (and (> i 1) (> (vector-ref (tas:tableau T) i) (vector-ref (tas:tableau T) (tas:pere i)))) (begin (tas:permute ! (tas:tableau T) i (tas:pere i)) (boucle (tas:pere i))) T)))) (define (tas:insere-sommet ! T v) (vector-set ! (tas:tableau T) 1 v) (let boucle ((i 1) (g 2) (d 3)) (if (or (and (<= g (tas:taille T)) (< (vector-ref (tas:tableau T) i) (vector-ref (tas:tableau T) g))) (and (<= d (tas:taille T)) (< (vector-ref (tas:tableau T) i) (vector-ref (tas:tableau T) d)))) (let ((m (if (> d (tas:taille T)) g (if (< (vector-ref (tas:tableau T) g) (vector-ref (tas:tableau T) d)) d g)))) (tas:permute ! (tas:tableau T) i m) (boucle m (tas:fils-gauche m) (tas:fils-droit m)))))) (define (tas:extraire T) (let ((res (vector-ref (tas:tableau T) 1)) (nouveau-sommet (vector-ref (tas:tableau T) (tas:taille T)))) (vector-set ! T 1 (- (tas:taille T) 1)) (tas:insere-sommet ! T nouveau-sommet) res))
On peut utiliser ces algorithmes pour déterminer quels sont les k plus petits éléments d'un flux de données de données. On commencerait construire un tas avec les k premiers éléments du tas. A 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.
(define (trier-liste L) (let ((T (tas:creer (length L)))) (let loop ((L L)) (if (not (null ? L)) (begin (tas:ajoute ! T (car L)) (loop (cdr L))))) (let loop ((L '())) (if (zero ? (tas:taille T)) L (loop (cons (tas:extraire T) L)))))) (define (trier-vecteur V) (let ((T (tas:creer (vector-length V)))) (do ((i 0 (+ i 1))) ((>= i (vector-length V))) (tas:ajoute ! T (vector-ref V i))) (do ((i (- (vector-length V) 1) (- i 1))) ((< i 0) V) (vector-set ! V i (tas:extraire T))))) (define (n-min V n) (if (<= (vector-length V) n) (trier-vecteur V) (let ((T (tas:creer n))) (do ((i 0 (+ i 1))) ((>= i n) T) (tas:inserer-sommet ! T (vector-ref V i))) (do ((i n (+ i 1))) ((>= i (vector-length V)) T) (entasser T (vector-ref V i))) (let ((W (make-vector n))) (do ((i 0 (+ i 1))) ((>= i n) W) (vector-set ! W (- (- n 1) i) (tas:extraire T)))))))
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.

<!—BEGIN NOTES document—>

---

1

Le Britannique C. Antony R. Hoare est à l'origine de quelques contributions de premier plan. Des études universitaires de tonalité plutôt littéraire lui ont donné l'occasion de partir en stage en 1960 dans le laboratoire d'Andreï Nikolaiévitch Kolmogorov à l'Université de Moscou pour travailler sur un projet de traduction automatique. Pour réaliser un dictionnaire électronique nécessaire à ce projet (par ailleurs vite abandonné) il inventa l'algorithme de tri « Quicksort » que tout étudiant en informatique se doit d'avoir étudié en détail et programmé. Ce stage lui avait donné le goût de la programmation, mais, comme il le raconte lui-même avec humour, il eut la chance que sa formation initiale lui fermât les portes du UK National Physical Laboratory, et il entra dans l'industrie. C'est là qu'il eut l'occasion de participer au développement de systèmes d'exploitation, domaine pour lequel il élabora la méthode des moniteurs de Hoare afin de contrôler les accès concurrents et exclusifs à des ressources partagées et la théorie des processus séquentiels communicants, encore aujourd'hui le seul modèle complet et cohérent qui excède réellement le modèle de von Neumann.

<!—END NOTES—> <!—HTMLFOOT—> <!—ENDHTML—> <!—FOOTER—>

---

This document was translated from L^AT_EX by H^EV^EA.