Nous allons voir dans ce chapitre l'utilisation du tri bulle boustrophédon pour trier un tableau d'entiers. Mais auparavant nous allons expliquer le tri à bulle (ou tri bulle) simple. Soit un tableau d'entiers non trié. Prenons par exemple :
9, 2, 15, 7, 3, 1, 6, 13, 17, 4
Le tri bulle consiste à parcourir le tableau de gauche à droite et chaque fois qu'on est sur un nombre, si son voisin droit a une valeur inférieure, alors on permute ces deux nombres. Une fois qu'on est au bout, si une permutation a eu lieu alors on recommence depuis le début.
Voici l'exemple: On est sur le premier nombre. Son voisin est plus petit que lui donc on les permute pour obtenir:
2, 9, 15, 7, 3, 1, 6, 13, 17, 4
Ensuite on avance pour tomber sur le deuxième nombre. Pas de permutation car 9<15. On avance. On est sur le troisième nombre. Comme 7<15 alors on les permute et on obtient :
2, 9, 7, 15, 3, 1, 6, 13, 17, 4
On passe ensuite au quatrième nombre qui est ici 3 et qui est plus petit que son voisin droit, donc on les permute:
2, 9, 7, 15, 1, 3, 6, 13, 17, 4
On continue, et on trouve une permutation à la dernière position :
2, 9, 7, 15, 1, 3, 6, 13, 4, 17
On est arrivé à la fin, mais des permutations ont eu lieu, donc on recommence depuis le début; voici les étapes successives:
position 1 : 2, 9, 7,
15, 1, 3, 6, 13, 4, 17 --> pas de
changement
position 2 : 2, 7,
9, 15, 1,3, 6, 13, 4, 17
position 3 : 2, 7, 9,
15, 1,3, 6, 13, 4, 17 --> pas de
changement
position 4 : 2, 7, 9, 1,
15, 3, 6, 13, 4, 17
position 5 : 2, 7, 9,
1, 3, 15, 6, 13, 4, 17
position 6 : 2, 7, 9,
1, 3, 6, 15, 13, 4, 17
position 7 : 2, 7, 9,
1, 3, 6, 13, 15, 4, 17
position 8 : 2, 7, 9,
1, 3, 6, 13, 4, 15, 17
position 9 : 2, 7, 9,
1, 3, 6, 13, 4, 15, 17 --> pas de
changement
Mais on a eu des permutations, donc on recommence
position 1 : 2, 7, 9,
1, 3, 6, 13, 4, 15, 17 --> pas de
changement
position 2 : 2, 7, 9,
1, 3, 6, 13, 4, 15, 17 --> pas de
changement
position 3 : 2, 7, 1,
9, 3, 6, 13, 4, 15, 17
position 4 : 2, 7, 1, 3,
9, 6, 13, 4, 15, 17
position 5 : 2, 7, 1,
3, 6, 9, 13, 4, 15, 17
position 6 : 2, 7, 1,
3, 6, 9, 13, 4, 15, 17 --> pas de
changement
position 7 : 2, 7, 1,
3, 6, 9, 4, 13, 15, 17
position 8 : 2, 7, 1,
3, 6, 9, 4, 13, 15, 17 --> pas de
changement
position 9 : 2, 7, 1, 3, 6, 9, 4, 13, 15, 17 --> pas de changement
A cette étape nous avons eu 4 permutations, donc on recommence:
position 1 : 2, 7, 1,
3, 6, 9, 4, 13, 15, 17 --> pas de
changement
position 2 : 2, 1,
7, 3, 6, 9, 4, 13, 15, 17
position 3 : 2, 1, 3,
7, 6, 9, 4, 13, 15, 17
position 4 : 2, 1, 3, 6,
7, 9, 4, 13, 15, 17
position 5 : 2, 1, 3,
6, 7, 9, 4, 13, 15, 17 --> pas de
changement
position 6 : 2, 1, 3,
6, 7, 4, 9, 13, 15, 17
position 7 : 2, 1, 3,
6, 7, 4, 9, 13, 15, 17 --> pas de
changement
position 8 : 2, 1, 3,
6, 7, 4, 9, 13, 15, 17 --> pas de
changement
position 9 : 2, 1, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
A cette étape nous avons eu 4 permutations, donc on recommence:
position 1 : 1, 2,
3, 6, 7, 4, 9, 13, 15, 17
position 2 : 1, 2, 3,
6, 7, 4, 9, 13, 15, 17 --> pas de
changement
position 3 : 1, 2, 3,
6, 7, 4, 9, 13, 15, 17 --> pas de
changement
position 4 : 1, 2, 3,
6, 7, 4, 9, 13, 15, 17 --> pas de
changement
position 5 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17
position 6 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17 --> pas de
changement
position 7 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17 --> pas de
changement
position 8 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17 --> pas de
changement
position 9 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
A cette étape nous avons eu 2 permutations, donc on recommence:
position 1 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17 --> pas de
changement
position 1 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17 --> pas de
changement
position 1 : 1, 2, 3,
6, 4, 7, 9, 13, 15, 17 --> pas de
changement
position 1 : 1, 2, 3, 4,
6, 7, 9, 13, 15, 17
position 5 : 1, 2, 3,
4, 6, 7, 9, 13, 15, 17 --> pas de
changement
position 6 : 1, 2, 3,
4, 6, 7, 9, 13, 15, 17 --> pas de
changement
position 7 : 1, 2, 3,
4, 6, 7, 9, 13, 15, 17 --> pas de
changement
position 8 : 1, 2, 3,
4, 6, 7, 9, 13, 15, 17 --> pas de
changement
position 9 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17 --> pas de changement
A cette étape nous avons eu une permutation, donc on recommence, et quand on arrive à la fin aucune permutation n'a été effectuée, donc le tableau est trié et le programme s'arrête. Le tri a été réalisé en 7 boucles.
On constate que la première amélioration possible est de limiter le
nombre d'avancées du curseur. En effet, chaque boucle sur les éléments du
tableau a pour effet de ramener le plus grand nombre rencontré à la fin du
tableau (ou à sa position correcte). Sachant donc qu'après le premier parcours
le nombre 17 se trouve à la fin, il ne sera plus nécessaire à l'étape suivante
d'aller jusqu'à 17, il suffira de s'arrêter à son prédécesseur. Ainsi à chaque
étape le nombre de paires à comparer diminue.
Mais on peut encore améliorer cet algorithme : c'est le tri bulle
boustrophedon.
Le parcours du tableau se fait alternativement de gauche à droite et de
droite à gauche.
Quand on va de gauche à droite (cas ci-dessus), le plus grand nombre se
trouve à l'extrémité droite du tableau (et la nouvelle extrémité devient don
prédécesseur).
Quand on va de droite à gauche, le plus petit nombre se trouve à
l'extrémité gauche du tableau et la nouvelle extrémité gauche devient son
successeur. Quand les deux extrémités se rejoignent, alors le tableau est trié
et le programme s'arrête. On peut aussi affirmer que si pendant un parcours (de
gauche à droite ou inversement) aucune permutation n'a lieu, alors le tableau
est trié.
Pour réaliser le tri bulle boustrophedon, nous allons réaliser deux procédures qui s'appellent l'une l'autre, d'où le nom de récursivité croisée.
Dans ce programme, nous allons utiliser une procédure de permutation de deux nombres. Voici un moyen d'échanger la valeur de deux nombres sans utiliser de variable auxiliaire :
soit deux variables a et b; a=3, b=5. On veut avoir à la fin a=5 et b=3.
On fait donc les opérations suivantes :
a
:= a + b = 8
b
:= a - b = 8 - 5 = 3
a
:= a - b = 8 - 3 = 5
Et comme on peut le constater, les deux valeurs sont échangées.
Nous allons voir les structures de données utilisées : le type "tab" qui est un tableau d'entiers, un tableau de type "tab" qui est un tableau de constantes (et que nous allons copier dans la variable "t2" pour pouvoir effectuer le tri dessus).
Comme on a une récursivité croisée, et comme nous n'avons pas utilisé la programmation orientée objet, il faut déclarer l'une des deux procédures en "forward".
type tab = array[1..10] of integer;
const t1: tab = (9, 2, 15, 7, 3, 1, 6, 13, 17, 4);
var t2: tab;
procedure arriere(var t: tab; limg, limd: integer); forward;
procedure affiche(t: tab);
var i: integer;
s: string;begin
s := '';
for i := 1 to 10 do
s := s + inttostr(t[i]) + '; ';
form1.memo1.lines.add(s);end;
procedure echange(var a, b: integer);
begin
a := a + b; b := a - b; a := a - b;end;
procedure avant(var t: tab; limg, limd: integer);
var permute: boolean;
i: integer;begin
permute := false;for i := limg to limd - 1 do
if t[i] > t[i + 1] then
beginechange(t[i], t[i + 1]);
permute := true; end; if permute then beginaffiche(t);
arriere(t, limg, limd - 1);
end;
end;
procedure arriere(var t: tab; limg, limd: integer);
var permute: boolean;
i: integer;begin
permute := false;for i := limd downto limg + 1 do
if t[i] < t[i - 1] then
beginechange(t[i], t[i - 1]);
permute := true; end; if permute then beginaffiche(t);
avant(t, limg + 1, limd);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
move(t1, t2, sizeof(t1));avant(t2, 1, 10);
end;
Télécharger le code source Delphi