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 premire 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 premire 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 !