program algorithmesDeTri;
uses crt;
const Taille_Max = 100;
type
    suiteEntiers = record
                      nbElements:integer;
                      elements : array[1..Taille_Max] of integer;
                end;
var s:suiteEntiers;  {pour memoriser les elements }
    choix:integer;  {pour le menu}
    fin:boolean; {pour arreter le programme}


procedure lireSuite(var s:suiteEntiers);
var i:integer;
begin

  repeat
        write('Nombre d''elements de la suite ? ');
        readln(s.nbElements);
  until ((s.nbElements>=0) and (s.nbElements<=Taille_Max));

  for i:=1 to s.nbElements
  do begin
     write('element[',i,'] ? ');readln(s.elements[i]);
     end;

end;


procedure afficherSuite(s:suiteEntiers);
var i:integer;
begin
     write('{');
     for i:=1 to s.nbElements
     do write(s.elements[i],' ');

     writeln('}');
end;

procedure triInsertionDicho(var s:suiteEntiers);
var x, i, pos:integer;

function rechercherPosRec(x:integer;debut,fin:integer;s:suiteEntiers):integer;
var milieu:integer;
begin
   if (debut<=fin)
   then begin
          milieu:=(debut+fin) div 2;
          if (x=s.elements[milieu])
          then rechercherPosRec:=milieu
          else if (x<s.elements[milieu])
               then rechercherPosRec:=rechercherPosRec(x,debut,milieu-1,s)
               else rechercherPosRec:=rechercherPosRec(x,milieu+1,fin,s)
        end
   else rechercherPosRec:=debut;
end;

procedure decalageDroite(pos,i:integer;var s:suiteEntiers);
var j:integer;
begin
     for j:=i downto pos+1
     do s.elements[j]:=s.elements[j-1];
end;

begin
     for i:= 2 to s.nbElements
     do begin
           x:=s.elements[i];
           pos:=rechercherPosRec(x,1,i-1,s);
           decalageDroite(pos,i,s);
           s.elements[pos]:=x;
        end;

end;

procedure triBulles(var s:suiteEntiers);
begin
end;


procedure triFusion(debut,fin:integer;var s:suiteEntiers);
var milieu:integer;

procedure fusionner(debut,milieu,fin:integer;s1:suiteEntiers;var s2:suiteEntiers);
var i,j,k:integer;
begin
 i:=debut; j:=milieu+1; k:=debut;
 while((i<=milieu) and (j<=fin))
 do begin
         if(s1.elements[i]<s1.elements[j])
         then begin
                   s2.elements[k]:=s1.elements[i];
                   i:=i+1;k:=k+1;
              end
         else begin
                   s2.elements[k]:=s1.elements[j];
                   j:=j+1;k:=k+1;
              end
    end;
    if (i>milieu)
    then begin
           while (j<=fin)
           do begin
                   s2.elements[k]:=s1.elements[j];
                   k:=k+1;j:=j+1;
              end
         end
    else begin
            while(i<=milieu)
            do begin
                  s2.elements[k]:=s1.elements[i];
                  k:=k+1;i:=i+1;
               end;
         end;

end;

begin
     if(debut<fin)
     then begin
               milieu:=(debut+fin) div 2;
               triFusion(debut,milieu,s);
               triFusion(milieu+1,fin,s);
               fusionner(debut,milieu,fin,s,s);
          end


end;

procedure triRapide(debut,fin:integer;var s:suiteEntiers);
var milieu:integer;

procedure echanger(var x,y:integer);
var aux:integer;
begin
 aux:=x;x:=y;y:=aux;
end;

procedure partitionner(debut,fin:integer;var s:suiteEntiers; var m:integer);
var i,pivot:integer;
begin

pivot:=s.elements[debut];
m:=debut;
for i:=debut+1 to fin
do if (s.elements[i]<pivot)
   then begin
          m:=m+1;
          echanger(s.elements[m],s.elements[i]);
        end;
echanger(s.elements[debut],s.elements[m]);
end;


begin
     if(debut<fin)
     then begin
               partitionner(debut,fin,s,milieu);
               triRapide(debut,milieu-1,s);
               triRapide(milieu+1,fin,s);
          end


end;


procedure menu(var choix:integer);
begin
     writeln('Tapez <1> pour tri insertion dichotomique');
     writeln('Tapez <2> pour tri a bulles');
     writeln('Tapez <3> pour tri fusion');
     writeln('Tapez <4> pour tri rapide');
     writeln('Tapez <5> pour quitter le programme');
     write('Votre choix? ');readln(choix);
end;

begin
fin:=false;
repeat
  clrscr;
  menu(choix);
  case choix of
  1: begin
           lireSuite(s);
           triInsertionDicho(s);
           writeln('La suite triee est : ');
           afficherSuite(s);
           readln;
     end;
  2: begin
           lireSuite(s);
           triBulles(s);
           writeln('La suite triee est : ');
           afficherSuite(s);
           readln;
     end;
  3: begin
           lireSuite(s);
           triFusion(1,s.nbElements,s);
           writeln('La suite triee est : ');
           afficherSuite(s);
           readln;
     end;
  4: begin
           lireSuite(s);
           triRapide(1,s.nbElements,s);
           writeln('La suite triee est : ');
           afficherSuite(s);
           readln;
     end;
  5: fin:=true;
   end;
until fin;
end.