IPEIEM 2013-2014

1ère année MP, PC, PT Page 1

Correction Série TD N° 5 : Tri des Tableaux

Exercice 1 [Tri par dénombrement] :

Question 1 :

Dérouler l'algorithme de tri par dénombrement sur le tableau : A [7, 1, 3, 1, 2, 4, 5,2, 4, 3]

Le tableau A de taille N = 10, commence par l’indice 1et peut contenir des valeurs nulles

La valeur maximale contenue dans A est K = 7

Le tableau D de taille K + 1 = 8, commence par l’indice 0

A [7, 1, 3, 1, 2, 4, 5, 2, 4, 3]

Phase 1: D = [0, 0, 0, 0, 0, 0, 0, 0]

Phase 2: D = [0, 2, 2, 2, 2, 1, 0, 1]

Phase 3: A = [1, 1, 2, 2, 3, 3, 4, 4, 5, 7]

Question 2 :

Procédure fréquence (A:TAB, D:tableau [0..k] d’entiers, N, k: entier) Var i : entier Début

Pour i de 0 à k faire D[i] ← 0 Fin pour Pour i de 1 à N faire D [A [i]] ← D [A [i]] + 1 Fin pour

Fin

Question 3 :

Procédure tri_dénombrement (VAR A:TAB ; D:tableau [0..K] d’entiers, N, k : entier) Var i, Indice : entier Début Indice ← 1

Pour i de 0 à k faire //parcourir le tableau D Pour j de 1 à D [i] faire

A [Indice] ← i Indice ← Indice + 1

Fin pour Fin pour

Fin

IPEIEM 2013-2014

1ère année MP, PC, PT Page 2

Exercice 2 : [Tri par comptage]

Question 1 :

Procédure comptage (T:TAB, N:entier, VAR C:TAB) Var i, j : entier Début Pour i de 1 à N faire C[i] ← 0 Pour j de 1 à N faire Si (T[j]>T[i]) alors C[i] ← C[i] + 1 Fin si Fin pour Fin pour Fin Question 2 :

Procédure tri_comptage (VAR T:TAB, N:entier) Var i, j : entier C:TAB Début Comptage (T, N, C) Indice ← 0 Répéter

Pour i de 1 à N faire Si (C[i] = indice) alors Permuter (C[i], C [indice + 1]) Permuter (T[i], T [indice + 1]) Fin si Fin pour

Indice ← Indice + 1 Jusqu’à (Indice = N)

Fin

IPEIEM 2013-2014

1ère année MP, PC, PT Page 3

Exercice 3 [Fusionnement de deux tableaux triés]:

// la variable « p » correspond à l’indice de fin du premier sous tableau trié.

Procédure tri_fusion (VAR T:TAB, N, p:entier) Var i, j: entier S:TAB Début

i ← 1 j ← p + 1 k ← 1 Tant que (i ≤ p et j ≤ N) faire

Si t[i] < t[j] alors s[k] ← t[i] ; i ← i+1

Sinon s[k] ← t[j] j ← j+1

fin si K ← k + 1

Fin tant que Si (i ≤ p) alors

Pour c de i à p faire S[k] ← t[c] K ← k + 1

Fin pour Sinon

Pour c de j à N faire S[k] ← t[c] K ← k + 1

Fin pour Fin si

Pour c de 1 à N faire T[c] ← S[c]

Fin pour Fin

IPEIEM 2013-2014

1ère année MP, PC, PT Page 4

Exercice 4 : [recherches séquentiel les renvoyant un indice]

La Spécification : c’est l’ensemble d’exigences à satisfaire par un produit ou un service. Si une ou

plusieurs des spécifications applicables ne sont pas satisfaites, il peut être désigné comme étant hors

spécification.

Dans notre exercice, si l'élément recherché est présent plusieurs fois dans le tableau, quel indice

renvoyer ? On peut renvoyer soit :

a. Premier indice : le plus petit indice

b. Dernier indice : le plus grand indice

c. Indice N° p, avec p donné en paramètre

d. Tous les indices, sous la forme d’un tableau d’entiers

Idem si cet élément n'est pas dans le tableau ?

Renvoyer un indice qui ne figure pas parmi les indices du tableau, soit :

a. Indice de début -1

b. Indice de fin + 1

c. Indice x fixé préalablement qui indique l’inexistence d’élément.

Cela permet, après l’appel à cette fonction, de tester si l’indice renvoyé n’appartient pas aux indices du

tableau, donc l’élément recherché n’existe pas

//Retourner le plus petit indice Fonction rech_seq_ppi (T:TAB, N, e:entier) : entier Var i : entier Début

i ← 1 Tant que (i ≤ N) faire

Si T[i] = e alors Retourner (i)

Fin si i ← i+1

Fin tant que Retourner (-1) Fin

IPEIEM 2013-2014

1ère année MP, PC, PT Page 5

//Retourner le plus grand indice Fonction rech_seq_pgi (T:TAB, N, e:entier) : entier Var i : entier Début

i ← N Tant que (i ≥ 1) faire

Si T[i] = e alors Retourner (i)

Fin si i ← i-1

Fin tant que Retourner (-1) Fin

Exercice 5 : [Recherche dichotomique]

Pour x=11, 3 comparaisons du tableau sont effectuées.

Pour x=12, 3 comparaisons du tableau sont effectuées.

Pour x=10, une seule comparaison du tableau est effectuée.

T = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22]

[0, 2, 4, 6, 8,] [12, 14, 16, 18, 20, 22] [10]

x = 11

[12, 14] [18, 20, 22] [16]

[12] [] [14]

IPEIEM 2013-2014

1ère année MP, PC, PT Page 6

Exercice 6 : [Recherche dichotomique renvoyant un indice]

Question 1 :

Fonction Recherche_dichotomique (T : TAB, N, x : entier) : entier

Variable bas, milieu, haut : entier Début bas ← 1;

haut ← N;

Rang ← -1;

Répéter

milieu ← (bas + haut) div 2;

Si x = T [milieu] alors

retourner (milieu)

Sinon

si T[milieu] < x alors

bas ← milieu + 1

sinon

haut ← milieu-1

fin si

fin si

Jusqu’à (bas > haut)

Retourner (-1)

Fin

Question 2 :

Le plus petit ? Le plus grand ?

On ne peut pas estimer si la fonction va renvoyer l’indice le plus petit ou le plus grand.

Car ça dépend de son emplacement par rapport au milieu du tableau.