Correction :« CC 1 »
Questions :
1- Soit le tableau suivant :
17 12 20 5 8 12 16 20 25 27 39 50 55 60 14 19
Proposer un nom d’algorithme pour trier efficacement ce tableau ? (justifier)
Réponse :
Le tri ‘insertion’ est le plus efficace CAR: Il contient la boucle ‘Tant que’ qui saute les cas ou les éléments
sont déjà triés. Ce tableau, représente déjà un certain tri.
2- Soit le tableau suivant :
7 12 20 25 28 30 36 38 45 47 59 60 65 70 77
En utilisant l‘algorithme de la recherche dichotomique en combien d’itérations de la boucle le
nombre 12 sera retrouvé? (justifier)
Réponse :
La boucle va faire 3 itérations pour trouver le nombre 12 :
La première itération: milieu=(0+14)/2= 7 → T[7]=38 38>12
La deuxième itération: milieu=(0+6)/2=3 → T[3]=25 25>12
La troisième itération : milieu=(0+2)/2=1 → T[1]=12 le nombre 12 est trouvé dans la
position =1
3- En comparant l’algorithme de la recherche séquentielle d’un élément X dans un tableau quelconque
avec l’algorithme de la recherche dichotomique, lequel est le plus efficace ? (justifier)
Réponse :
Le tableau est quelconque donc on peut pas comparer les deux algorithmes :
L’algorithme de la recherche dichotomique nécessite que la tableau soit dèjé trié. Et l’algorithme de la
recherche séquentielle peut s’effectuer sur un tableau quelconque.
1/4
Exercice 2:
On considère l’algorithme du tri suivant :
Procédure proc (tableau tab[N]:entier )
variables
nbrElt, i, stop, temp:entier ;
Début
NbrElt ← n-1;
Tant que (nbrElt > 0)
i ← 0; stop ← 0;
tant que (i < nbrElt)
si (tab[i] > tab[i+1]) alors
temp ← tab[i];
tab[i] ← tab[i+1];
tab[i+1]← temp;
stop ← i;
finSi
i ← i + 1;
finTantque
nbrElt ← stop;
finTantque
Fin.
1) Expliquer le principe du tri de cet algorithme.
Réponse :
C’est le tri à bulle ou par propagation :
Le tri est réalisé en propageant par permutations successives le plus grand élément du tableau à la
fin de celui-ci, c.a.d comparer les éléments consécutifs d'un tableau, et les permuter lorsqu'ils
sont mal triés.
Durant la première itération de la boucle externe, Le plus grand élément gagne de proche en proche
l'extrémité droite du tableau et se retrouve à la fin de l’itération dans la dernière case du tableau.
Ce principe est répété pour chacun des éléments jusqu’à ce que tout le tableau soit trié,
2/4
2) Calculer sa complexité si le tableau en entrée est déjà trié .(justifier)
Procédure proc (tableau tab[N]:entier )
variables
nbrElt, i, stop, temp:entier ;
Début
NbrElt ← n-1; :2
Tant que (nbrElt > 0) :1 (évalue Vrai) + 1 (évalué Faux)
i ← 0; stop ← 0; :2
tant que (i < nbrElt) : n-1 (évalue Vrai) + 1 (évalué Faux)
si (tab[i] > tab[i+1]) alors : 2 * (n-1)
temp ← tab[i]; :0
tab[i] ← tab[i+1]; :0
tab[i+1]← temp; :0
stop ← i; :0
finSi
i ← i + 1; : 2 * (n-1)
finTantque
nbrElt ← stop; :1
finTantque
Fin.
Réponse :
T(n) = 2 + 1 + 1 + 2 + n-1 + 1 + 2*(n-1) + 2*(n-1) + 1
T(n) = 5 * n + 3
T(n) = O (n)
La complexité de cet algorithme si le tableau en entrée est déjà trié est linéaire.
3/4
3) Calculer sa complexité si le tableau en entrée est trié à l’inverse.(justifier)
Procédure proc (tableau tab[N]:entier )
variables
nbrElt, i, stop, temp:entier ;
Début
1 : NbrElt ← n-1;
2 : Tant que (nbrElt > 0)
3: i ← 0; stop ← 0;
4: tant que (i < nbrElt)
5: si (tab[i] > tab[i+1]) alors
6: temp ← tab[i];
7: tab[i] ← tab[i+1];
8: tab[i+1]← temp;
9: stop ← i;
10 : finSi
11 : i ← i + 1;
12 : finTantque
13 : nbrElt ← stop;
14 : finTantque
Fin.
Réponse :
1: 2
1ère itération de la boucle 2ème itération de la boucle … jusqu’à la (n-1)ème itération
externe Tant que : externe Tant que : de la boucle externe Tant que :
2: :1 2: :1 2: :1
3: :2 3: :2 3: :2
4: : (n-1) ‘évalué Vrai’ + 1 ‘évalué Faux’ 4: : (n-2) ‘évalué Vrai’ + 1 ‘évalué Faux’ 4: : (1) ‘évalué Vrai’ + 1 ‘évalué Faux’
5: : 2 * (n-1) 5: : 2 * (n-2) 5: :2*1
6: : 1 * (n-1) 6: : 1 * (n-2) 6: :1*1
7: : 2 * (n-1) 7: : 2 * (n-2) 7: :2*1
8: : 2 * (n-1) 8: : 2 * (n-2) 8: :2*1
9: : 1 * (n-1) 9: : 1 * (n-2) 9: :1*1
11 : : 2 * (n-1) 11 : : 2 * (n-2) 11 : : 2 * 1
13 : 1 13 : 1 13 : 1
T(n) = 2 + 1* (n-1) + 2 * (n-1) + 11* Somme( de i allant de 1 jusqu’à (n-1)) + 1 * (n-1) + 1 * (n-1)
T(n) = 2 + 5* (n-1) + 11 * ( n * (n-1))/2
T(n) = 11/2 * n2 – n/2 - 3
T(n) = O(n2 )
La complexité de cet algorithme si le tableau en entrée est trié à l’inverse est quadratique.
4/4
