Algorithmes et programmation en Pascal

On parcourt le tableau et on s'arrête dès que x est trouvé ou que la fin du tableau est atteinte.

Première implémentation

FUNCTION cherche1 (v : vec_t; vn, x : integer) : boolean;
VAR i : integer;
BEGIN
i := 1;
while (i <= vn) and (v[i] <> x) do
i := i+1;
cherche1 := i <= vn;

END;

On sort du while dans deux situations :

• Si i > vn, on a parcouru tout le tableau sans trouver x.
• Sinon i <= vn et v[i] = x : on a trouvé x.

On ne peut donc pas écrire comme résultat cherche1 := v[i] = x puisque ipeut sortir du tableau ; c'est pourquoi on écrit cherche1 := i <= vn.

Il y a un problème : dans le while, l'expression (i <= vn) and (v[i] <> x)est toujours complètement évaluée, même si le premier terme est faux.

En éffet, le and ne signifie pas « et sinon», comme dans d'autres langages.

La conséquence est que si x n'est pas dans v, à la dernière itération on évaluera (vn+1 <= vn) and (v[vn+1] <> x) et on sortira du vecteur !

Implémentation à éviter absolument.

Deuxième implémentation avec un booléen

On va décomposer le test dans le while

FUNCTION cherche2 (v : vec_t; vn, x : integer) : boolean;
VAR i : integer;
continuer : boolean;
BEGIN
i := 1; continuer := true;
while continuer do
if i > vn
then continuer := false
else if v[i] = x
then continuer := false
else i := i+1;
cherche2 := i <= vn;
END;

Troisième implémentation

FUNCTION cherche3 (v : vec_t; vn, x : integer) : boolean;
VAR i : integer;
BEGIN
i := 1;
while (i < vn) and (v[i] <> x) do { i < n strict }
i := i+1;
cherche3 := v[i] = x;
END;

On sort toujours du while avec i <= vn, donc on ne sort jamais du tableau.

Par contre pour le résultat, il faut changer le test, et on a le droit d'écrire

cherche3 := v[i] = x .

Le coût : Le vecteur v étant non trié, il faut

• vn itérations six n'appartient pas à v
• vn/2 itérations en moyenne si x appartient à v.

Lorsqu'on parle de vecteur trié, on suppose toujours que les vecteurs sont triés

par ordre croissant : pour tout i; v[i] <= v[i + 1].

On parcourt le tableau et on s'arrête dès que :

• x est trouvé
• ou la fin du tableau est atteinte
• ou v[i] > x : ça veut dire que tous les éléments qui suivent seront plus grands que x, inutile de continuer.

On peut adapter facilement la méthode 3 :

FUNCTION cherche4 (v : vec_t; vn, x : integer) : boolean;
VAR i : integer;
BEGIN
i := 1;
while (i < vn) and (v[i] < x) do { v[i] < x strict }
i := i+1;
cherche4 := v[i] = x;
END;

Le coût Le vecteur v étant trié, il faut en moyenne vn/2 itérations, que x appartienne ou non à v.

Jeu1 L'ordinateur choisit un prix secret entre 1 et 1000 F, et le joueur doit le deviner en un nombre minimum de coups.

PROCEDURE jeu1 (secret : integer);
VAR n, essai : integer;
continuer : boolean;
BEGIN
continuer := true; n := 1;
while continuer do
begin
write ('Essai ', n, ' : '); readln (essai);
if essai < secret then writeln ('+')
else if essai > secret then writeln ('-')
else begin
writeln ('Gagné en ', n, ' coups');
continuer := false;
end;
n := n+1;
end;
END;

Ce qui nous intéresse c'est la stratégie du joueur : admettons que secret = 326.

La solution est trouvée en seulement 9 coups !

C'est le principe de la dichotomie : on a un intervalle de possibilités, et à chaque

Itération on réduit de moitié la taille de cet intervalle.

De la sorte, le nombre maximum d'itération est log2(vn), c'est à dire 10 pour vn =1000, de 20 pour vn = 1 million.

Jeu2 La réciproque : l'utilisateur choisit un prix secret entre 1 et 1000 F, et l'ordinateur doit le deviner en un nombre minimum de coups.

Le programme va donc gérer un intervalle de possibilités, c'est à dire un début et une fin, proposer le milieu de l'intervalle, puis changer l'intervalle en fonction de la réponse.

La recherche dichotomique consiste à faire la même chose sur les indices, et est

donc très performante : sur l'exemple du correcteur orthographique, il faudra 20

Itérations pour trouver un mot, donc 40 000 itérations pour corriger tout le texte, ce qui est quasiment instantané.

La dichotomie se fait toujours sur un vecteur trié.

Cela consiste à considérer une certaine plage de recherche inf.. sup sur le vecteur, plage que l'on réduit d'un facteur 2 à chaque itération.

Au départ, la plage de recherche est tout le vecteur.

A une itération donnée, on a une plage [inf..sup] et son milieu est m := (inf + sup) div 2.

On a donc la subdivision : [inf..m-1], [m], [m+1..sup].

• Soit v[m] = x et on a fini.
• Soit v[m] < x, donc x 62 [inf..m] et la nouvelle plage sera [m+1..sup].
• Soit v[m] > x, donc x 62 [m..sup] et la nouvelle plage sera [inf..m-1].

On implémente l'algorithme avec un booléen trouve.

FUNCTION cherche5 (v : vec_t; vn, x : integer) : boolean;
VAR inf, sup, m : integer;
trouve : boolean;
BEGIN
trouve := false;
inf := 1; sup := vn;
while (inf <= sup) and not trouve do
begin
m := (inf + sup) div 2;
if v[m] = x
then trouve := true
else if v[m] < x
then inf := m+1
else sup := m-1;
end;
cherche5 := trouve;
END;

Remarque Le fait de prendre m-1 ou m+1 n'est pas une simple optimisation, mais est essentiel pour que l'algorithme se termine.

Le coût Il faut

• log2 vn itérations si x n'appartient pas à v.
• log2 vn itérations au plus si x appartient à v.

On peut améliorer l'efficacité dans le cas où x n'appartient pas à v :

BEGIN
trouve := false;
if (v[1] <= x) and (x <= v[vn]) then
begin
inf := 1; sup := vn;
while {...}
end;
cherche6 := trouve;
END;

La méthode consiste à sélectionner des minimums successifs dans v, et à les ranger au fur et à mesure dans w.

Au départ on recherche quel est le max.

A chaque pas :

• on cherche min(v)
• on le met au bout de w
• on le remplace dans v par max(v)

Exemple Trier dans l'ordre alphabétique les lettres du mot 'ETABLES'.

Le max est la lettre 'T'.

FUNCTION maximum (v : vec_t; vn : integer) : char;
VAR i : integer; m : char;
BEGIN
m := v[1];
for i := 2 to vn do
if v[i] > m then m := v[i]:
maximum := m;
END;
FUNCTION ind_min (v : vec_t; vn : integer) : integer;
VAR i, j : integer;
BEGIN
j := 1;
for i := 2 to vn do
if v[i] < v[j] then j := i:
ind_min := j;
END;
PROCEDURE tri_remplacement ( v : vec_t;
vn : integer;
var w : vec_t );
VAR max : char;
i, j : integer;
BEGIN
{ recherche du max }
max := maximum (v,vn);
58 Algorithmes et programmation en Pascal Edouard Thiel
{ pas a pas }
for i := 1 to vn-1 do
begin
j := ind_min (v,vn);
w[i] := v[j];
v[j] := max;
end;
{ on met le max dans la derniere case }
w[vn] := max;
END;

Le coût

Les performances sont faibles : il y a environ vn*vn comparaisons, et 2,5vn affectations en moyenne.

Par exemple si vn= 1000, on aura 1 000 000 de comparaisons et 2500 affectations.

Dans la méthode précédente, la place occupée est double ; on peut éviter de créer un nouveau vecteur en travaillant directement sur v.

Principe on est à l'étape i.

• Supposons déjà trié v[1..i-1], et non traité v[i..vn].
• On cherche le min dans v[i..vn]
• On le permute avec v[i].
• Maintenant v[1..i] est trié.

Exemple Trier les lettres du mot 'ETABLES'.

Le coût

Les performances sont meilleures que le tri par remplacement : il y a environ

Vn*vn/ 2 comparaisons, et vn / 2 permutations en moyenne.

Par exemple si vn= 1000, on aura 500 000 comparaisons et 1500 affectations.

C'est une variante du tri par permutation, un peu moins efficace ; il y a une version optimisée qui est un peu meilleure que le tri par permutation.

Principe On est à l'étape i.

• Supposons déjà trié v[1..i-1], et non traité v[i..vn].
• On parcourt v[i..vn] en descendant et, chaque fois que deux éléments consécutifs ne sont pas dans l'ordre, on les permute.
• En fin de parcours le min de v[i..vn] se retrouve dans v[i].
• Maintenant v[1..i] est trié.

Le nom du « tri à bulles» vient de ce que à chaque étape i, les éléments les plus «légers » remontent vers la surface, sont transportés à gauche.

On constate aussi qu'à chaque étape, l'ordre général est accru.

Tri à bulle optimisé

Si lors d'une étape i, aucune permutation n'a lieu, c'est que [i..vn] est déjà dans l'ordre, et le tri est fini.

Booléen apermute ou encore mieux, indice dp de dernière permutation.

Cette méthode consiste à construire un vecteur d'indices ind, où l'on calcule la position que devrait avoir chaque élément pour que le vecteur soit trié.

Exemple Résultat sur le tri des lettres du mot 'ETABLES'.

PROCEDURE tri_comptage ( v : vec_t;
vn : integer;
var w : vec_t);
VAR i, k : integer;
ind : array [1..VMax] of integer;
BEGIN
{ init }
for i := 1 to vn do ind[i] := 1;
{ construit ind }
for i := 1 to vn-1 do
for k := i+1 to vn do
if v[k] < v[i]
then ind[i] := ind[i]+1
else ind[k] := ind[k]+1;
60 Algorithmes et programmation en Pascal Edouard Thiel
{ construit w }
for i := 1 to vn do w[ind[i]] := v[i];
END;

Le coût

La place occupée est importante (3 vecteurs).

Le nombre de comparaisons est constant (vn*(vn-1)/2). C'est du même ordre que le tri par permutation ou à bulles non optimisé.

Il y a très peu d'affectations (vn) ; cela est très intéressant si les éléments de vn sont «  lourds », par exemple des strings ou des records triés sur un champ.

Pour insérer un élément x en queue de v, il suffit de faire

if vn < VMax then
begin vn := vn+1; v[vn] := x; end;

Si on veut insérer x à une autre position, c'est que l'on considère que le vecteur est trié avec un certain ordre (croissant, décroissant, d'apparition, etc.).

On veut insérer x à la position i dans v, avec 1 <= i <= vn.

On doit décaler v[i..vn] vers la droite :

if vn < VMax then
begin
vn := vn+1;
for j := vn downto i+1 do { en descendant }
v[j] := v[j-1];
v[i] := x;
end;

On veut supprimer l'élément v[i], avec 1 <= i <= vn.

Si l'ordre des éléments dans v est indifférent, on place l'élément de queue dans le trou.

v[i] := v[vn]; { si i = vn, ca ne fait rien }
vn := vn-1;

On décale v[i+1..vn] vers la gauche :

décale v[i+1..vn] vers la gauche :
for j := i to vn-1 do { en montant }
v[j] := v[j+1];
vn := vn-1;