Algorithmique impérative/Tri

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 ?

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.

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

Une implémentation testable en Pascal

program tris;

const
	DEB = 0;
	FIN = 5;

type
	T_tabint = array [DEB..FIN] of integer;

procedure permuter(var i : integer; var j : integer);
(* à la fin, i vaut le j donné et j vaut le i donné *)
var
	tmp : integer; (* un tampon pour stocker l'élément que va remplacer l'élément minimum pendant l'inversion *)
begin
	tmp := i;
	i := j;
	j := tmp
end;

procedure afficher(var t : T_tabint);
(* procédure qui affiche le tableau passé en paramètre *)
(* sur une ligne et sous la forme [a|b|c|d...|l|m] *)

var
	i : integer; (* variable de boucle *)
begin
	write('[');
	for i := DEB to FIN-1 do write(t[i],'|');
	write (t[FIN],']');
end;

procedure remplir(var t : T_tabint);
(* procédure qui remplit le tableau passé en paramètre *)
(* avec des nombres aléatoires pris entre 0 et 99 *)

var
	i : integer; (* variable de boucle *)
begin
	for i := DEB to FIN do t[i] := random(99);
end;


procedure TriSelection(var t : T_tabint);
var
	i, j	: integer;	(* variables de boucle *)
	min		: integer;	(* indice du plus petit élément parmi ceux qui reste à trier *)
	
begin
   for i:=DEB to FIN-1 do begin
      min := i;
      for j:=i+1 to FIN do
         if (t[j] < t[min]) then min:=j;

      if (i <> min) then permuter(t[i],t[min]);
   end; 
end;

procedure TriBulle(var t: T_tabint);
var
	i, j	: integer;	(* variables de boucle *)
 
begin
  for i:=DEB to FIN-1 do begin
    j := i+1;
    for j := FIN-1 downto i do
    	if t[j+1]<t[j] then permuter(t[j],t[j+1]);
  end;
end;

var
	tab : T_tabint;

begin

	(* pour chaque tri on recrée un tableau aléatoire, on l'affiche *)
	(* puis on le trie et on l'affiche à nouveau *)

	(* Tri sélection *)
	writeln('TRI SELECTION');
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	TriSelection(tab);
	afficher(tab);
	writeln(' <- tableau trié');
		
	(* Tri bulle *)
	writeln('TRI BULLE');
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	TriBulle(tab);
	afficher(tab);
	writeln(' <- tableau trié');
	
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é