Corrigé du TD n° 8 1) Tri par fusion 1.1) Il faut faire une seule boucle sur l'indice de T, disons i, et dans cette boucle il faut parcourir, à l'aide de deux autres indices, disons j et k, les deux tableaux à fusionner. A chaque itération de la boucle, on compare T1[j] et T2[k] et on insère le plus petit dans T[i]. Par exemple : i1 <- 1 i2 <- 1 pour i de 1 à n1 + n2 si i1 <= n1 et i2 <= n2 si T1[i1] < T2[i2] T[i] <- T1[i1] i1 <- i1 + 1 sinon T[i] <- T2[i2] i2 <- i2 + 1 sinon # un des deux tableaux est épuisé si i1 <= n1 T[i] <- T1[i1] i1 <- i1 + 1 sinon T[i] <- T2[i2] i2 <- i2 + 1 1.2) O(n1 + n2) 1.3) trier(T, debut, fin) si fin - debut > 1 milieu <- (fin + debut)/2 trier(T, debut, milieu) trier(T, milieu + 1, fin) fusionner(T, debut, milieu, milieu + 1, fin) # On utilise un tableau d'appui F, qui pourra être réutilisé pour toutes les fusions fusionner(T, d1, f1, d2, f2) i1 <- d1 ; n1 <- f1 - d1 + 1 i2 <- d2 ; n2 <- f2 - d2 + 1 pour i de 1 à n1 + n2 si i1 <= f1 et i2 <= f2 si T[i1] < T[i2] F[i] <- T[i1] i1 <- i1 + 1 sinon F[i] <- T[i2] i2 <- i2 + 1 sinon # un des deux tableaux est épuisé si i1 <= n1 F[i] <- T[i1] i1 <- i1 + 1 sinon F[i] <- T[i2] i2 <- i2 + 1 pour i de 1 à n1 + n2 T[d1 + i - 1] <- F[i] trifusion(T, n) trier(T, 1, n) 2) L'algorithme trie le tableau T de façon décroissante 3.1) tableau initial : 122, 12, 22, 342, 111, 731, 428, 513, 23, 5 itération 1 : on trie (avec un algorithme stable) sur le chiffre des unités : -> 111, 731, 122, 12, 22, 342, 513, 23, 5 itération 2 : on trie sur le chiffre des dizaines : -> 5, 111, 12, 513, 122, 22, 23, 731, 342 itération 3 : on trie sur le chiffre des centaines : -> 5, 12, 22, 23, 111, 122, 342, 513, 731 tri terminé. 3.2) La performance du tri par base est O(d*n), où n est la taille de la collection d'objets à trier et d est le nombre de chiffres (ou caractères) de la clef la plus longue. Or, pour les mêmes données, le choix d'une base b, entraîne une longueur des clefs proportionnelle à 1/log b. Par exemple, un nombre qui en base 256 s'écrit en 4 "chiffres", s'écrira en 10 chiffres en base 10 et en 32 chiffres en base 2. Donc, plus la base est grande, moins d'itérations il faudra faire; par contre, plus la base est grande, plus d'inversions il faudra faire pour chaque tri (c'est parce qu'il y a plus de valeurs possibles pour chaque chiffre !) et donc chaque tri prendra plus de temps. 4.1) Tri par comptage 4.2) Tri par comptage 4.3) Tri par insertion 4.4) Tri par insertion ou par sélection 4.5) Tri fusion ou tri par tas