Algorithmique impérative/Tri

Un livre de Wikibooks.

Sections

[modifier] Problématique

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 ?

[modifier] Solution

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.

[modifier] Une solution "simple"

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).

[modifier] Une implémentation testable en Pascal

  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é
Récupérée de « http://fr.wikibooks.org/wiki/Algorithmique_imp%C3%A9rative/Tri »