with Ada.Text_IO, ada.integer_text_io, Ada.Numerics.Discrete_Random;
use Ada.Text_IO, ada.integer_text_io;
procedure TD2 is
max_val : constant := 99;
n : constant := 10;
type T_Array is array (1..n) of integer;
procedure swap(a,b : in out integer) is
v : integer;
begin
v := a;
a := b;
b := v;
end;
procedure Put(a : in T_Array) is
begin
for i in a'range loop
put(a(i), 3);
end loop;
new_line;
end;
procedure test(b : Boolean; s : String; nberreur : in out integer) is
begin
put(s); put(" : ");
if b then
put("ok !");
else
nberreur := nberreur + 1;
put("failed !");
end if;
New_Line;
end;
subtype random_range is integer range 0..max_val;
package random_int is new Ada.Numerics.Discrete_Random(random_range);
use random_int;
procedure genere(a : in out T_Array) is
Gen : Generator;
begin
Reset(Gen);
for i in a'Range loop
a(i) := Random(Gen);
end loop;
end;
function sorted(a : in T_Array) return Boolean is
begin
for i in a'first..a'last-1 loop
if a(i) > a(i + 1) then
return false;
end if;
end loop;
return true;
end;
-- tri par insertion tp2ex2a
procedure tri_insertion1(a : in out T_Array) is
v : Integer;
pos : Natural;
begin
for i in 1..a'last - 1 loop
-- valeur ˆ classer
v := a(i + 1);
-- au mieux nous sommes sur la bonne position
pos := 1;
-- recherche de la position d'insertion
for j in reverse 1..i loop
if v > a(j) then
pos := j + 1;
exit;
end if;
end loop;
-- decalage des valeurs pos..i -> pos+1..i+1
for j in reverse pos..i loop
a(j + 1) := a(j);
end loop;
a(pos) := v;
end loop;
end;
-- tri par insertion tp2ex2b
procedure tri_insertion2(a : in out T_Array) is
v : Integer;
pos : Natural;
nbcomp : natural := 0;
begin
for i in 1..a'last - 1 loop
-- valeur ˆ classer
v := a(i + 1);
-- au pire nous insŽrons ˆ la premire position
pos := 1;
-- recherche de la position d'insertion et dŽcalage sinon
for j in reverse 1..i loop
nbcomp := nbcomp + 1;
if v > a(j) then
pos := j + 1;
exit;
else
a(j + 1) := a(j);
end if;
end loop;
a(pos) := v;
end loop;
put("Nbcomp : "); put(nbcomp, 0); New_line;
end;
-- tri par insertion tp2ex2c
-- recherche dichotomique de la position d'insertion
procedure tri_insertion3(a : in out T_Array) is
v : Integer;
pos, g, d, n : Natural;
nbcomp : natural := 0;
begin
for i in 1..a'last - 1 loop
-- valeur ˆ classer
v := a(i + 1);
-- au pire nous insŽrons ˆ la premire position
pos := 1;
-- recherche de la position si non triŽ de 1..i+1
nbcomp := nbcomp + 1;
if v < a(i) then
g := 1;
d := i;
while d - g > 1 loop
nbcomp := nbcomp + 1;
n := (g + d) / 2;
if a(n) < v then
g := n;
else
d := n;
end if;
end loop;
nbcomp := nbcomp + 1;
if v < a(g) then
pos := g;
else
pos := g+1;
end if;
-- decalage des valeurs pos..i -> pos+1..i+1
for j in reverse pos..i loop
a(j + 1) := a(j);
end loop;
a(pos) := v;
end if;
end loop;
put("Nbcomp : "); put(nbcomp, 0); New_line;
end;
t, t1, t2, t3, t4, t5 : t_array;
pos : natural;
nberreur : integer := 0;
nbtest : natural := 1000;
begin
for i in 1..nbtest loop
genere(t);
put(t);
t1 := t;
tri_insertion1(t1);
put(t1);
test(sorted(t1), "tri_insertion1", nberreur);
t2 := t;
tri_insertion2(t2);
put(t2);
test(sorted(t2), "tri_insertion2", nberreur);
t3 := t;
tri_insertion3(t3);
put(t3);
test(sorted(t3), "tri_insertion3", nberreur);
new_line;
end loop;
put("Nb erreur : "); put(nberreur);
end TD2;
-- 63 39 35 14 30 4 95 72 78 2
-- 2 4 14 30 35 39 63 72 78 95
--tri1 : ok !
-- 2 4 14 30 35 39 63 72 78 95
--tri2 : ok !
-- 2 4 14 30 35 39 63 72 78 95
--tri3 : ok !
--strIsIn("ab", "aab", pos) = 2 : ok !
--strIsIn("a", "aab", pos) = 1 : ok !
--strIsIn("abc", "aab", pos) = 0 : ok !
--strIsIn("ce", "Ce qu'on laisse sur la table fait plus de bien que ce qu'on y prend.", pos) = 52 : ok !
--strIsIn("table", "Ce qu'on laisse sur la table fait plus de bien que ce qu'on y prend.", pos) = 1 : ok !