with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;

procedure Quick_Sort is 

  type Tab is array (Integer range <>) of Integer; 
  type T_Sous_Liste is 
     record 
        Debut : Integer;  
        Fin   : Integer;  
     end record; 

  procedure Ecrire (L : in Tab ) is 
  begin
    Put("[");
    Put(L(L'First),Width => 3);

    for K in L'First+1 .. L'Last loop
      Put(";");
      Put(L(K),Width => 3);
    end loop;
    Put("]");
  end Ecrire;


  procedure Tri_Pivot (T : in out Tab ) is 
    N : Integer := T'First;  
    M : Integer := T'Last;  

    procedure Piv (L : in  T_Sous_Liste ) is 
      I   : Integer := 0;       -- place pivot             
      P   : Integer := 0;       -- valeur pivot             
      D   : Integer := L.Debut;  
      F   : Integer := L.Fin;  
      Tmp : Integer := 0;  

    begin
      if F - D <= 0 then return; end if;

      I:=(L.Debut + L.Fin)/2;
      P:=T(I); -- a partir de mainanant I pointe vers une case vide
      Ecrire(T);

      Put(D,Width => 3);
      Put(F,Width => 3);
      put("  val_pivot = "); Put(p,Width => 3);
      New_Line;

      while D < F loop

        while D < I and then T(D) < P loop D:= D + 1; end loop;

        while F > I and then T(F) > P loop F:= F - 1; end loop;

        exit when D=F;

        if F = I then
          T(F) := T(D); I := D; F := F - 1;
        elsif D = I then
          T(D) := T(F); I := F; D := D + 1;
        else
					Tmp := T(D); T(D) := T(F); T(F) := Tmp;
					F := F - 1;	D := D + 1;
        end if;
      end loop;--on sort qd D = F

      T(D) := P;

      Ecrire(T); new_line; new_line;
      Piv((L.Debut, D - 1)); Piv((F + 1, L.Fin));

    end Piv;

  begin

    Piv((N, M));

  end Tri_Pivot;

  T1 : Tab(1..12):=  (2, 9, 3, 42, 1, 5,61,4,12,6,13,15); 

begin
  
  Tri_Pivot(T1);

end Quick_Sort;