(* Procedure qui affichage un tableau de taille n *)
procedure affichage(T : array of integer;n:integer);
var
   i,compteur : integer;
begin
   compteur := 0;
   writeln('');
   for i:= 0 to (n-1) do
   begin
      write('|',T[i]);
      compteur := compteur +1;
      if compteur mod 20=0 then
      begin
	 compteur := 0;
	 writeln('');
      end;
   end;
   writeln('');
end; { affichage }
(* Question 1 *)
(*  Procedure echange
 *  description Procedure qui échange 2 cases d'un tableau d'entier
 *  auteur AOUSTON Francois
 *  date 15/02/2012
 *  PréConditions : T: Tableau d'entier, i et j sont les indices des cases à échanger.  *)
procedure echange(var T :array of integer; i,j:integer);
var
   tmp : integer;
begin
   tmp := T[i];
   T[i] := T[j];
   T[j] := tmp;
end; { echange }
(*Question 2
 * Tri par selection, ordre croissant,tri lent *)
(*  Procedure : TriSelection
 *  Description : Procedure qui réalise le tri d'un tableau d'entier par selection.
 *  Auteur : AOUSTON Francois
 *  date : 15/02/2012
 *  PréConditions : T est le tableau d'entier à trier, n est la taille de ce tableau, boolTps est un booléen qui recoit vrai lorsque l'on active le mode chronomètre et qui recoit faux lorsqu'on veut afficher le tri du tableau étape par étape.
 *)
Procedure TriSelection(var T : array of integer; n: integer; boolTps:boolean);
var
   i,j,posmin : integer;
begin
   for i := 0 to (n-2) do
   begin
      posmin := i;
      for j := (i+1) to (n-1) do
      begin
	 if (T[j] <  T[posmin]) then
	    posmin := j;
      end;
      if (posmin <> i) then
      begin
	 echange(T,i,posmin);
	 if  not (boolTps) then
	 begin
	    writeln('Etape : ',i);
	    affichage(T,n);
	 end;
      end;
   end;
end; { TriSelection }
(* Question 3
 *  Tri a bulle, ordre croissant, tri lent *)
(*  Procedure : TriBulle
 *  Description : Procedure qui réalise le tri à bulle d'un tableau d'entier.
 *  Auteur : AOUSTON Francois
 *  date : 15/02/2012
 *  PréConditions : T est le tableau d'entier à trier, n est la taille de ce tableau, boolTps est un booléen qui recoit vrai lorsque l'on active le mode chronomètre et qui recoit faux lorsqu'on veut afficher le tri du tableau étape par étape.
 *)
Procedure TriBulle(var T : array of integer; n:integer; boolTps: boolean);
var
   desordre : boolean;
   i	    : integer;
begin
   desordre := TRUE;
   while desordre do
   begin
      desordre := FALSE;
      for i := 0 to (n-2) do
	 if T[i] > T[i+1] then
	 begin
	    desordre := TRUE;
	    echange(T,i,i+1);
	    if  not (boolTps) then
	       affichage(T,n);
	 end;
   end;
end; { TriBulle }
(* Question 4
 *  Tri par Insertion, ordre croissant, tri lent *)
(*  Procedure : TriInsertion
 *  Description : Procedure qui réalise le tri d'un tableau d'entier par insertion.
 *  Auteur : AOUSTON Francois
 *  date : 15/02/2012
 *  PréConditions : T est le tableau d'entier à trier, n est la taille de ce tableau, boolTps est un booléen qui recoit vrai lorsque l'on active le mode chronomètre et qui recoit faux lorsqu'on veut afficher le tri du tableau étape par étape.
 *)
Procedure TriInsertion(var T : array of integer; n:integer; boolTps: boolean);
var
   i,j	 : integer;
begin
   for i := 1 to (n-1) do
   begin
      j := i;
      while (j>1) and (T[j] < T[j-1]) do
      begin
	 echange(T,j,j-1);
	 j := j-1;
	 if  not (boolTps) then
	 begin
	    writeln('Etape : ',i);
	    affichage(T,n);
	 end;
      end;
   end;
end; { TriInsertion }

(* Question 5
 Tri Bicolore : Il n'y a que 2 valeurs possibles dans le tableau *)
(*  Procedure : TriBicolore
 *  Description : Procedure qui réalise le tri bicolore d'un tableau d'entier.
 *  Il n'y a que 2 entiers différents dans tout le tableau.
 *  Auteur : AOUSTON Francois
 *  date : 15/02/2012
 *  PréConditions : T est le tableau d'entier à trier, n est la taille de ce tableau, boolTps est un booléen qui recoit vrai lorsque l'on active le mode chronomètre et qui recoit faux lorsqu'on veut afficher le tri du tableau étape par étape.
 *  Post-conditions: valmin est la plus petite valeur du tableau, valmax la plus grande, compteur permet de calculer ne nombre de case contenant valmin.
 *)
procedure TriBicolore(var T : array of integer;n:integer;boolTps:boolean);
var
  valmin,valmax, compteur,i : integer;
begin
   compteur := 0;
   valmin :=T[0];
   valmax := T[1];
   for i := 0 to (n-1) do
   begin
      if T[i]< valmin then
	 valmin := T[i]
     else  if T[i]>valmax then
	 valmax := T[i];
   end;
   for i := 0 to (n-1) do
   begin
      if T[i] = valmin then
	 compteur := compteur +1;
   end;
   for i := 0 to (compteur-1) do
      T[i] := valmin;
   for i := compteur to (n-1) do
      T[i] := valmax;
end; { tribicolore }
(* Question Bonus
 *  Question numéro 7, tri rapide par ordre croissant *)
Function Partitionner(var T : array of integer; debut,fin:integer):integer;
var
   i,j,pivot : integer;
begin
   pivot := T[debut];
   i := debut;
   j := fin+1;
   repeat
      repeat
	 i := i+1;
      until (T[i] >= pivot);
      repeat
	 j := j-1;
      until (T[j] <= pivot );
      if (i<j) then
	 echange(T,i,j);
   until i>=j;
   T[debut] := T[j];
   T[j] := pivot;
   Partitionner := j;
end; { Partitionner }
Procedure TriRapide(var T : array of integer;n:integer;debut,fin:integer);
var
   pivot : integer;
begin
   if (debut<fin) then
   begin
      pivot := Partitionner(T,debut,fin);
      TriRapide(T,n,debut,pivot-1);
      TriRapide(T,n,pivot+1,fin);
   end;
end; { TriRapide }

(* Question 6
 *  Menu permettant de choisir le type de tri ainsi que le mode d'affichage *)
(*  Procedure : Menu
 *  Description : Procedure qui demande a l'utilisateur quel type de tri utiliser et s'il veut activer le mode chronomètre ou non. S'il l'active, alors on affiche le temps en milliseconde durant lequel le tri s'est éxecuté.
 *  Auteur : AOUSTON Francois
 *  date : 15/02/2012
 *  PréConditions : T est le tableau d'entier à trier, n est la taille de ce tableau, boolTps est un booléen qui recoit vrai lorsque l'on active le mode chronomètre et qui recoit faux lorsqu'on veut afficher le tri du tableau étape par étape.
 *)
Procedure Menu(tab : array of integer;n:integer;var boolTps:boolean );
var
   debut : TDateTime;
   choix : integer;
begin
   choix := 0;
   clrscr;
   writeln('1 : Affichage etape par etape du tri ');
   writeln('2 : Affichage a la fin du tri ainsi que mode chronométré.');
   writeln('');
   writeln('Choisissez votre mode d''affichage.');
   readln(choix);
   boolTps := choix=2;
   choix := 0;
   clrscr;
   textcolor(red);
   writeln('   -----------------------------    ');
   writeln('        Tri de tableaux                ');
   writeln('   +---------------------------+  ');
   writeln('1  |   Tri par selection       |   ');
   writeln('2  |   Tri à Bulle             |   ');
   writeln('3  |   Tri par Insertion       |   ');
   writeln('4  |   Tri Bicolore            |   ');
   writeln('5  |   Tri Rapide              |   ');
   writeln('6  |   Tri par fusion          |   ');
   writeln('7  |   Quitter                 |   ');
   writeln('   +---------------------------+  ');
   writeln('                                  ');
   textcolor(white);
   lowvideo;
   writeln('    +-------------------------+     ');
   writeln('    | Que voulez-vous faire ? |      ');
   writeln('    +-------------------------+     ');
   readln(choix);
   clrscr;
   boolTps := (choix=5)or (choix=4) or (choix=6) or (boolTps);
   debut := now;
   case choix of
     1 : TriSelection(tab,n,boolTps);
     2 : TriBulle(tab,n,boolTps);
     3 : TriInsertion(tab,n,boolTps);
     4 : TriBicolore(tab,n,boolTps);
     5 : TriRapide(tab,n,0,n-1);
     6 : TriFusion(tab,0,n-1);
     7 : writeln('Au revoir ');
   end; { case }
   if boolTps then
   begin
      writeln('Voici le résultat final du tri : ');
      affichage(tab,n);
      writeln('Le test s''est effectué en ',MilliSecondSpan(now,debut),' millisecondes.');
   end;
end;

(* debut du pogramme *)
var
tab			  : array of integer;
okSaisie,boolTps		  : boolean;
repTaille, encore : char;
taille			  : integer;
begin
   boolTps := FALSE;
 writeln('Bienvenue au programme de test de tri.');
   repeat
      // Initialisation du tableau à trier selon le choix utilisateur
      repeat
	 okSaisie := TRUE;
	 writeln('Sur quelle taille de tableau voulez-vous passer vos tests ?');
	 writeln(' 1 : 8');
	 writeln(' 2 : 12');
	 writeln(' 3 : 20');
	 writeln(' 4 : 72');
	 writeln(' 5 : 112');
	 writeln(' 6 : 234');
	 writeln(' 7 : 542');
	 writeln(' 0 : bicolore');
	 readln(repTaille);
	 case repTaille of
	   '1' : tab := tab8;
	   '2' : tab := tab12;
	   '3' : tab := tab20;
	   '4' : tab := tab72;
	   '5' : tab := tab112;
	   '6' : tab := tab234;
	   '7' : tab := tab542;
	   '0' : tab := tabDrap
	 else okSaisie := FALSE;
	 end; { case }
      until okSaisie;
	 taille := length(tab);
	 menu(tab,taille,boolTps);
	 // Encore une fois ?
	 writeln('Voulez-vous faire un autre test ? (n, pour arreter)');
	 readln(encore);
      until (lowerCase(encore)='n') ;
      writeln('Merci d''avoir utilise notre programme de test de tri, a bientot !');
end.