Objectifs

•       Construction de boucle par récurrence
•       Tris
•       Fonctions et procédures

Exercice 1

Enoncé

Tri par recherche séquentielle d'un tableau T(a..b) d'entiers : on suppose qu'une partie du tableau T(a..i-1) est triée. L'idée est de parcourir le tableau
T(i..b) de manière séquentielle à la recherche du plus petit élément (disons T(j)). Il suffit ensuite de permuter T(i) avec T(j) et de recommencer la recherche
sur le tableau T(i+1..b).
 

-- Tri par recherche séquentielle d'un tableau T(a..b)
-- Idée : on suppose que le tableau T(a..i) est trié
-- Il suffit de rechercher le plus petit élément dans T(i+1..b)
-- Soit T(j) cet élément, on le permute avec T(i+1)
--
--
-- Raisonnement
-- 1-INVARIANT : T(a..i-1) trie et T(i..b) non trie
-- 2-CAI i=b
-- 3-CORPS de BOUCLE
--  rechercher le plus petit élément dans T(i..b)->T(j)
--  permuter T(i) et T(j)
-- 4-INITIALISATION i=a (en considérant que le tableau trié est vide initialement ((i-1)-a)+1))
--

-- Algorithme du tri d'un tableau T
debut
    pour i=a à b-1 faire
        T(j)<- rechercherPlusPetit(T(i..b)
        permuter(T(j),T(i))
    fin pour;
fin;

-- Algorithme de recherche du plus petit élément d'un tableau T
debut
    min<-premier élément du tabeau T;
    pour  chaque élément du tableau T faire
        si cet élément est inférieur à min alors l'affecter à min; fin si;
    fin pour;
fin;

-- Programme
with Ada.Text_io;use Ada.Text_io;
with Ada.Integer_Text_io;use Ada.Integer_Text_io;

procedure triSeq is
 type Tableau is array(Integer range <>) of Integer;
 procedure permuter(x,y:in out Integer) is
 z:Integer:=x;
 begin
  x:=y;
  y:=z;
 end permuter;

 function rechercherPlusPetit(T:Tableau) return Integer is
  min:Integer:=T'first;
 begin
  for i in T'first..T'last loop
   if T(i)<T(min) then min:=i;end if;
  end loop;
  return min;
 end rechercherPlusPetit;

 procedure tri(T:in out Tableau) is
 begin
  for i in T'first..T'last loop
   declare
    IndiceDuPlusPetit:Integer:=rechercherPlusPetit(T(i..T'last));
   begin
    permuter(T(i),T(IndiceDuPlusPetit));
   end;
  end loop;
 end tri;

 procedure put(T:in Tableau) is
 begin
  put("(");
  for i in T'range loop
   put(T(i),width=>3);
  end loop;
  put(")");
 end put;

 tab:Tableau(1..5):=(4,7,1,9,2);

begin
 new_line;
 put(tab);
 new_line;
 tri(tab);
 put(tab);
 new_line;
end triSeq;