With Text_io;
With Ada.Numerics.Discrete_Random;
WITH Calendar;

Procedure Labo is
 
  --
  -- Implanter les tris simples 
  --
  USE TYPE Calendar.Time;	-- Pour pouvoir utiliser l'opérateur "-" dans Ada.Calendar
  
  Max_element : Constant Natural := 20000; 

  SUBTYPE Intervalle IS Natural range 1..Max_Element;
  Type Tab_entier is array(1..Max_element) of natural; 

  Tab       : Tab_Entier;
  Tab_Copie : Tab_Entier;
  Package Generer_Nombre is new Ada.Numerics.Discrete_Random (Intervalle);
  
 ------------------------------------------------------------
 Procedure Initialiser (Tab : out Tab_Entier) is

  -- initialiser le tableau avec des nombres entiers
 
   Germe : Generer_nombre.Generator;    
 Begin
   For i in tab'range loop
     tab (i) := Generer_Nombre.Random (Germe);
     Text_io.put_line (integer'image(tab(i)));
   End Loop;
 End Initialiser;
 
-----------------------------------------------------
 
PROCEDURE TriInsertion(tab : IN OUT Tab_Entier; nbEchanges : OUT Natural; temps : OUT Calendar.Day_Duration) IS
    j		: Natural;
    tmp 	: Natural;
    debut	: Calendar.Time;
BEGIN
    nbEchanges := 0;
    debut := Calendar.Clock;
    FOR i IN tab'First + 1..tab'Last LOOP
        j := i;
        WHILE j > tab'First AND THEN tab(j) < tab(j - 1) LOOP
            tmp := tab(j);
            tab(j) := tab(j - 1);
            tab(j - 1) := tmp;
            j := j - 1;
            nbEchanges := nbEchanges + 1;
        END LOOP;
    END LOOP;
    temps := Calendar.Clock - debut;
END TriInsertion;

-----------------------------------------------------

PROCEDURE TriSelection(tab : IN OUT Tab_Entier; nbEchanges : OUT Natural; temps : OUT Calendar.Day_Duration) IS
    indicePlusPetit : Natural;
    tmp 			: Natural;
    debut			: Calendar.Time;
BEGIN
    nbEchanges := 0;
    debut := Calendar.Clock;
    FOR i IN tab'First..tab'Last - 1 LOOP
        indicePlusPetit := i;
        FOR j IN i + 1..tab'Last LOOP
            IF tab(j) < tab(indicePlusPetit) THEN
				indicePlusPetit := j;
            END IF;
            tmp := tab(i);
            tab(i) := tab(indicePlusPetit);
            tab(indicePlusPetit) := tmp;
            nbEchanges := nbEchanges + 1;
        END LOOP;
    END LOOP;
    temps := Calendar.Clock - debut;
END TriSelection;

-----------------------------------------------------

PROCEDURE TriBulles(tab : IN OUT Tab_Entier; nbEchanges : OUT Natural; temps : OUT Calendar.Day_Duration) IS
    tmp		: Natural;
    debut	: Calendar.Time;
BEGIN
    nbEchanges := 0;
    debut := Calendar.Clock;
    FOR i IN tab'Range LOOP
        FOR j IN REVERSE i + 1..tab'Last LOOP
            IF tab(j) < tab(j - 1) THEN
                tmp := tab(j);
                tab(j) := tab(j - 1);
                tab(j - 1) := tmp;
                nbEchanges := nbEchanges + 1;
            END IF;
        END LOOP;
    END LOOP;
    temps := Calendar.Clock - debut;
END TriBulles;


nbEchanges	: Natural;
temps		: Calendar.Day_Duration;

Begin
  
  Text_io.new_line(2);
  Text_io.Put_line ("L A B O  - Universite du Quebec a Montreal");
  Text_io.Put_line ("           Laboratoire sur les tris");
  Text_io.new_line(2);

  Initialiser(Tab);
  Tab_Copie := Tab;   -- prendre une copie du tableau avant de le trier
  
  TriSelection(tab, nbEchanges, temps);
  Text_IO.Put_Line("Tri selection : " & Natural'Image(nbEchanges) & " echanges, " & Calendar.Day_Duration'Image(temps) & " secondes");
  
  Tab := Tab_Copie;   -- remise du tableau dans son etat d'avant le tri
  
  TriBulles (Tab, nbEchanges, temps);
  Text_IO.Put_Line("Tri bulles : " & Natural'Image(nbEchanges) & " echanges, " & Calendar.Day_Duration'Image(temps) & " secondes");
    
  Tab := Tab_Copie;   -- remise du tableau dans son etat d'avant le tri
  TriInsertion(tab, nbEchanges, temps);
  Text_IO.Put_Line("Tri insertion : " & Natural'Image(nbEchanges) & " echanges, " & Calendar.Day_Duration'Image(temps) & " secondes");
End Labo;