ds elec

program tri_a_bulles;

uses CRT;
const taille=20000;

var choix:byte;
premier,dernier:word;


    tableau:array[1..taille]of integer;

{sous programme d'enregistrement de valeurs aleatoires dans le tableau}
procedure enregistrer;

var i:word;

    begin
      for i:=1 to taille do
        tableau[i]:= random(taille*10);

    end;

{sous programme d'affichage des valeurs de la variable tableau}
procedure afficher;

var i:word;

    begin

    for i:=taille-50 to taille do
        writeln('tableau [',i,']= ',tableau[i]);

    readln;
    end;


procedure trier;
          var i,tampon:word;
              trie:boolean;
         

    begin
   
    repeat
    trie:=true;
    for i:=1 to taille-1 do
    if tableau[i]>tableau[i+1] then
                                begin
                                tampon:=tableau[i];
                                tableau[i]:=tableau[i+1];
                                tableau[i+1]:=tampon;
                                trie:=false;
                                end;
    until trie;
   
    end;
   
procedure Tri(premier,dernier:word);
var bas,haut:word;
    sep,mem:integer;

begin

  bas:=premier;
  haut:=dernier;
  sep:=tableau[(premier+dernier) DIV 2];
 
  repeat
        while tableau[bas]<sep do
        begin
        bas:=bas+1;
        end;
        while tableau[haut]>sep do
        begin
        haut:=haut-1;
        end;
       
        if bas<=haut then
        begin
        mem:=tableau[bas];
        tableau[bas]:=tableau[haut];
        tableau[haut]:=mem;
        bas:=bas+1;
        haut:=haut-1;
        end;
    until bas>haut;
if premier<haut then Tri(premier,haut);
if bas<dernier then Tri(bas,dernier);

end;

procedure rechercher;

          var nombre_cherche,i:integer;

          begin
              write('entrer le nombre cherche');
              readln(nombre_cherche);writeln;
              i:=0;
              repeat
              i:=i+1;
              until (nombre_cherche=tableau[i]) or (i=taille+1);
                  if i<taille+1 then writeln('la valeur ',nombre_cherche,' a ete trouvee en ',i,' ieme position')
                  else writeln('la valeur n''a pas ete trouvee');
                readln;
          end;

procedure rech_dich;

var centre,extreme1,extreme2,chercher:integer;


    begin
        extreme1 :=0;
        extreme2 :=taille;

        writeln('entrer la valeur cherchee');
        readln(chercher);writeln();
        repeat
              centre:= (extreme1+extreme2) div 2;
                  if  tableau[centre] < chercher then extreme1 := centre+1;
                  if  tableau[centre] > chercher then extreme2 := centre-1;
        until (tableau[centre]=chercher) or (extreme2<extreme1);
              if tableau[centre]=chercher then
                                          begin
                                          writeln('la valeur ',chercher,' a ete trouvee en ',centre,' ieme position');
                                        end
                                        else
                                            begin
                                            writeln('la valeur n''a pas ete trouvee');
                                        end;

        readln;

    end;

   

{debut du programme principal, avec appels des differents sous-programmes}

begin


    repeat
    premier:=1;
    dernier:=taille;
    clrscr;
    gotoxy(25,10);write('1-Enregistrer');
    gotoxy(25,12);write('2-Afficher');
    gotoxy(25,14);write('3-Trier');
    gotoxy(25,16);write('4-Tri rapide');
    gotoxy(25,18);write('5-Rechercher');
    gotoxy(25,20);write('6-Recherche Dichotomique');
    gotoxy(25,22);write('7-Quitter');
    gotoxy(25,24);readln(choix);
    case choix of
          1:Enregistrer;
          2:Afficher;
          3:Trier;
          4:Tri(premier,dernier);
          5:rechercher;
          6:rech_dich;
          end;
    until choix=7;
end.