Algorithmique impérative/Tri

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche
Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

Voici un problème fondamental d'informatique.

Supposons qu'il soit déclaré tab, un tableau.

Pour écrire le programme on prendra la déclaration suivante

 var
   tab : tableau MIN à MAX de T

Pour simplifier le problème, vous pourrez considérer que T = entier.

Note : sachez toutefois que les opérateurs <, <=, >, >= sont génériques et permettent de comparer toutes données tant qu'elles font partie du même ensemble ordonné (Par exemple : l'alphabet).

Question subsidiaire : considérez le cas particulier où les éléments sont distincts. L'algorithme fonctionne-t-il ?

Solution[modifier | modifier le wikicode]

Il est tout d'abord important de savoir qu'il existe de nombreuses façon de procéder. Pour connaitre ces algorithmes de tri, élément important de la culture de tout algorithmicien, nous vous invitons à consulter l'article « Algorithme de tri » sur Wikipédia ainsi que les articles sur les différents algorithmes de tri existants.

Pour vous corriger : vérifiez que votre algorithme ne tombe pas sur une erreur courante en supposant que tous les entiers sont distincts. En effet, il est facile de faire un algorithme qui, voulant inverser deux éléments pour les remettre en ordre, boucle sans fin en voulant inverser sans fin : lorsqu'il tombe sur deux éléments égaux.

Une solution "simple"[modifier | modifier le wikicode]

Le tri par sélection est un des plus simples algorithmes de tri. Il consiste à rechercher le plus petit (ou le plus grand) élément du tableau et de le placer à sa place définitive : au début (ou à la fin du tableau). Une fois un tel élément placé à sa place définitive, on recommence avec le reste du tableau. Lorsqu'on place un élément, on n'écrase pas ce qui était là (on perdrait un élément du tableau) mais on le déplace à la position qu'on vient de libérer (ce qui revient à faire une permutation).

Une implémentation testable en Pascal[modifier | modifier le wikicode]

 1 program tris;
 2 
 3 const
 4 	DEB = 0;
 5 	FIN = 5;
 6 
 7 type
 8 	T_tabint = array [DEB..FIN] of integer;
 9 
10 procedure permuter(var i : integer; var j : integer);
11 (* à la fin, i vaut le j donné et j vaut le i donné *)
12 var
13 	tmp : integer; (* un tampon pour stocker l'élément que va remplacer l'élément minimum pendant l'inversion *)
14 begin
15 	tmp := i;
16 	i := j;
17 	j := tmp
18 end;
19 
20 procedure afficher(var t : T_tabint);
21 (* procédure qui affiche le tableau passé en paramètre *)
22 (* sur une ligne et sous la forme [a|b|c|d...|l|m] *)
23 
24 var
25 	i : integer; (* variable de boucle *)
26 begin
27 	write('[');
28 	for i := DEB to FIN-1 do write(t[i],'|');
29 	write (t[FIN],']');
30 end;
31 
32 procedure remplir(var t : T_tabint);
33 (* procédure qui remplit le tableau passé en paramètre *)
34 (* avec des nombres aléatoires pris entre 0 et 99 *)
35 
36 var
37 	i : integer; (* variable de boucle *)
38 begin
39 	for i := DEB to FIN do t[i] := random(99);
40 end;
41 
42 
43 procedure TriSelection(var t : T_tabint);
44 var
45 	i, j	: integer;	(* variables de boucle *)
46 	min		: integer;	(* indice du plus petit élément parmi ceux qui reste à trier *)
47 	
48 begin
49    for i:=DEB to FIN-1 do begin
50       min := i;
51       for j:=i+1 to FIN do
52          if (t[j] < t[min]) then min:=j;
53 
54       if (i <> min) then permuter(t[i],t[min]);
55    end; 
56 end;
57 
58 procedure TriBulle(var t: T_tabint);
59 var
60 	i, j	: integer;	(* variables de boucle *)
61  
62 begin
63   for i:=DEB to FIN-1 do begin
64     j := i+1;
65     for j := FIN-1 downto i do
66     	if t[j+1]<t[j] then permuter(t[j],t[j+1]);
67   end;
68 end;
69 
70 var
71 	tab : T_tabint;
72 
73 begin
74 
75 	(* pour chaque tri on recrée un tableau aléatoire, on l'affiche *)
76 	(* puis on le trie et on l'affiche à nouveau *)
77 
78 	(* Tri sélection *)
79 	writeln('TRI SELECTION');
80 	remplir(tab);
81 	afficher(tab);
82 	writeln(' <- tableau donné');
83 	TriSelection(tab);
84 	afficher(tab);
85 	writeln(' <- tableau trié');
86 		
87 	(* Tri bulle *)
88 	writeln('TRI BULLE');
89 	remplir(tab);
90 	afficher(tab);
91 	writeln(' <- tableau donné');
92 	TriBulle(tab);
93 	afficher(tab);
94 	writeln(' <- tableau trié');
95 	
96 end.

Voici un exemple d'exécution :

TRI SELECTION
[54|58|70|83|59|84] <- tableau donné
[54|58|59|70|83|84] <- tableau trié
TRI BULLE
[53|83|41|61|63|38] <- tableau donné
[38|41|53|61|63|83] <- tableau trié