Exercices de tri de vecteurs – Éléments de corrigéLaurent Bloch |
Voici des éléments de corrigé pour l’examen BNF103 de juin 2013. Vous avez le code : pour répondre aux questions sur le nombre d’évaluations de telle ou telle expression, vous pouvez placer des compteurs et faire l’expérience. Et mettre vos observations à la disposition de chacun en rédigeant un commentaire au présent article. Merci !
L’exposé des questions et leurs solutions doivent une partie de leur inspiration à l’excellent manuel Informatique et sciences du numérique pour les terminales S, de Gilles Dowek, Jean-Pierre Archambault et alii.
Question 1Tri par sélection
Nous voulons définir un algorithme qui permette de trier un tableau A dont les indices vont de 0 à longueur(A)-1. Pour cela nous allons procéder par étapes. La première sera numérotée 0, la seconde 1, etc...
Au cours d’une étape donnée i nous considérerons que les éléments du tableau jusqu’à l’élément numéro i−1 sont triés et nous chercherons dans les éléments de numéro i, i+1, ... longueur(A)−1 le plus petit, nous échangerons alors cet élément avec l’élément de numéro i puis nous recommencerons.
Nous allons, pour commencer, écrire la fonction qui trouve le plus petit parmi les éléments de numéro i, i+1, ... longueur(A)−1.
Exercice 1.1
Nous voulons écrire la fonction Scheme minr telle qu’un appel à (minr A i) permette de trouver l’indice du plus petit élément de A entre i et longueur(A)-1. Voici l’algorithme MinR qui permet d’obtenir ce résultat :
-
Écrire une fonction Scheme qui implémente cet algorithme :
1 (define (minr A i) 2 (let ((imin i)) 3 (do ((j (+ i 1) (+ j 1))) 4 ((>= j (vector-length A)) imin) 5 (if (> (vector-ref A imin) 6 (vector-ref A j)) 7 (set! imin j))))) - 1.1.1 Combien de fois le test de la ligne 8 (du pseudo-code) sera-t-il exécuté ?
n-i fois.
- 1.1.2 Combien de fois l’affectation de la ligne 9 du pseudo-code sera-t-elle exécutée dans le pire des cas, dans le meilleur des cas, en moyenne ?
Si le vecteur est déjà trié : 0 fois. Si le vecteur est trié en ordre inverse : à chaque itération.
- 1.1.3 Quand la ligne 9 est exécutée que peut-on dire de la relation entre A[i] et les valeurs des cases précédentes du tableau ?
Exercice 1.2
La fonction Scheme suivante réalise l’algorithme du tri par sélection:
1 (define (tri-select A) 2 (do ((i 0 (+ i 1))) 3 ((>= i (vector-length A)) A) 4 (let ((j (minr A i))) 5 (let ((tmp (vector-ref A j))) 6 (vector-set! A j (vector-ref A i)) 7 (vector-set! A i tmp))))) |
Écrire maintenant le pseudocode de l’algorithme de tri par sélection.
Exercice 1.3
Combien de fois l’algorithme de tri par sélection fait-il appel à l’algorithme MinR ?
n fois. Comme MinR est un algorithme en O(n), en fait l’algorithme de tri par sélection est en O(n2).
Tri par fusion
L’algorithme de tri par fusion repose sur un autre algorithme qui consiste à fusionner deux tableaux déjà triés.
Exercice 2.1
Soient par exemple les deux tableaux ci-dessous :
1 T1 : (4, 7, 11, 17) 2 T2 : (5, 6, 12, 24) |
alors le résultat de leur fusion est :
1 T3 : (4, 5, 6, 7, 11, 12, 17, 24) |
On suppose les tableaux de même taille. Voici l’algorithme de fusion :
1 Algo : Fusion 2 Données : T1, T2 : deux tableaux de taille L 3 x <- 0 : y <- 0 4 Résultat : T3 : tableau de taille 2*L 5 pour i allant de 0 à 2*L - 1 faire 6 si x < L et y < L et T1[x] <= T2[y] 7 ou y = L 8 alors 9 T3[i] <- T1[x] 10 x <- x+1 11 sinon 12 T3[i] <- T2[y] 13 y <- y+1 14 finsi 15 fait 16 retourner T3 |
Cet algorithme calcule, l’une après l’autre, les valeurs contenues dans les cases du tableau T3. x est l’indice qui parcourt les cases de T1, y l’indice qui parcourt les cases de T2.
On considère la première case de T1 et la première case de T2. Si la valeur contenue dans la première case de T1 est la plus petite, on la copie dans la première case de T3 et on fait progresser x, sinon on copie dans la première case de T3 la valeur contenue dans la première case de T2 et on fait progresser y.
Au départ le tableau T3 est vide, on peut l’initialiser par exemple au moyen de la forme suivante :
1 (let ((T3 (make-vector (* L 2) 0))) 2 ... |
Écrire le programme Scheme qui implémente cet algorithme.
Exercice 2.2
Muni de ce programme Fusion, nous pouvons l’utiliser pour trier un tableau. Pour la suite des opérations nous supposerons que les tableaux à trier ont un nombre de cases égal à une puissance de deux : si ce n’était pas le cas nous nous y ramènerions en complétant le tableau par un nombre suffisant de cases, remplies avec des valeurs très grandes, qui se retrouveraient dans les dernières cases du tableau trié.
Soit par exemple un tableau de 8 cases : nous allons considérer que chaque case est un sous-tableau de une case, que nous appellerons un segment. Comme chaque segment (ou sous-tableau) n’a qu’une case, il est déjà trié !
Nous allons donc pouvoir fusionner chaque segment avec son voisin, et nous obtiendrons ainsi 4 segments de deux cases, triés. En recommençant nous aurons 2 segments de 4 cases, triés. Et ainsi de suite.
L’exercice proposé consiste d’abord à trier à la main, par cette méthode, le tableau suivant :
1 T : (12, 4, 2, 6, 7, 5, 22, 17) |
Soit L la longueur du vecteur à trier.
Lseg est la longueur de segment (qui est multipliée par 2 à chaque étape du calcul).
À chaque étape, on commence par fusionner les deux premiers segments, qui sont T[0..Lseg-1] et T[Lseg..2*Lseg-1], puis les deux suivants, qui sont :
T[2*Lseg..3*Lseg-1] et T[3*Lseg..4*Lseg-1], etc. Par exemple si on est à l’étape où Lseg vaut 2, les segments successifs sont :
1 T[0..1] T[2..3] T[4..5] T[6..7] |
Le programme Scheme qui implémente l’algorithme de tri par fusion est le suivant, à compiler, si le fichier est nommé tri-vect-fusion.scm, par la commande bigloo tri-vect-fusion.scm -o tri-vect-fusion, et l'exécutable sera tri-vect-fusion :
La variable b a pour valeur initiale l’indice dans le tableau du premier élément du premier segment de l’étape en cours.
Combien de fois sera appelée la procédure fusion-segments à la ligne 26 ?
Exercice 2.3
Il nous faut adapter le programme de fusion de vecteurs triés au tri de segments contigus, ce sera le programme fusion-segments.
On considère le segment de longueur Lseg, qui commence en T[b], parcouru par l’indice x, et son voisin, qui commence en T[b+Lseg], parcouru par l’indice y. Le programme fusion-segments construit le nouveau segment trié Tres, puis le recopie au bon endroit (c’est-à-dire à partir de T[b]) dans T par la procédure copy-seg-vect! :
Combien de fois, pour chaque invocation de fusion-segments, sera appelée la procédure copy-seg-vect! à la ligne 8 ? Soit au total, pour tri-fusion ?
Écrire l’algorithme en pseudo-code pour les procédures tri-fusion et copy-seg-vect!. L’écriture du pseudo-code de la procédure fusion-segments est facultative.
Que peut-on dire des performances comparées de tri-select! et de tri-fusion ?
La procédure tri-fusion comporte deux boucles imbriquées, ce qui suggère une complexité en n2, mais observons que pour la boucle la plus externe la taille des segments à fusionner double à chaque itération, ce qui fait que le nombre d’itérations est divisé par deux à chaque fois. La complexité de l’algorithme de tri-fusion est donc en O(n.logn), ce qui est meilleur que le tri par sélection.
Pour observer effectivement cette amélioration, il faut prendre de grands vecteurs, sinon la différence est imperceptible, voire dans l’autre sens. Cf. ci-dessous le programme pour construire de grands vecteurs remplis de nombres aléatoires. N’oubliez pas, leur taille doit être une puissance de 2, sinon cela ne marche pas !
Dans le programme proposé, la procédure fusion-segments comporte la création d’un vecteur de la taille du nouveau segment à chaque itération, ce qui est logique mais coûteux. On perdrait en élégance, mais on gagnerait en performance, en ayant une variable globale.
Ce document a été traduit de LATEX par HEVEA