Sys.command "ocaml -version";;
On s'intéresse à deux algorithmes de tris. Pour plus de détails, voir les pages Wikipédia (ou le [Cormen] par exemple) :
On veut implémenter les deux et les comparer, sur plein d'entrées.
(** Un échange T[i] <-> T[j]. Utilise une valeur temporaire *)
let swap tab i j =
let tmp = tab.(i) in
tab.(i) <- tab.(j);
tab.(j) <- tmp
;;
Le tri à bulle a une complexité en $\mathcal{O}(n^2)$ dans le pire des cas et en moyenne. Il a l'avantage d'être en place.
let tri_bulle cmp tab =
let n = Array.length tab in
for i = n - 1 downto 1 do
for j = 0 to i - 1 do
if cmp tab.(j + 1) tab.(j) < 0 then
swap tab (j + 1) j;
done
done
;;
On utilise une fonction de comparaison générique. La fonction compare (Pervasives.compare) fonctionne pour tous les types par défaut.
Une version plus efficace existe aussi (voir ces explications).
let tri_bulle_opt cmp tab =
let n = Array.length tab in
let i = ref 0 in
let last_swap = ref (-1) in
while !i < n - 1 do
(* séquence d'échanges sur T[i..n]: *)
last_swap := n - 1;
for j = n-1 downto !i + 1 do
if cmp tab.(j) tab.(j-1) < 0 then begin
swap tab j (j-1);
last_swap := j - 1
end;
(* i avance "plus vite" :*)
i := !last_swap + 1;
done
done
;;
(** Taille max des éléments dans les tableaux aléatoires *)
let maxint = int_of_float(1e3);;
(** Créer un tableau aléatoire. En O(n). *)
let rand_array length =
Array.init length (fun _ -> Random.int maxint)
;;
(** Vérifie que chaque élément du tableau n'y est qu'une seule fois (test l'égalité <> et pas !==).
Mal codé, en O(n^2). *)
let isInjArray tab =
try begin
Array.iteri (fun i x ->
(Array.iteri (fun j y ->
assert( (x<>y) || (i=j) )
) tab)
) tab;
true
end
with _ -> false
;;
(** En moyenne, est en O(n^2) si [maxint] est bien plus grand que [n]. *)
let rand_array_inj = function
| 0 -> [||]
| length ->
let tab = ref (rand_array length) in
while not(isInjArray (!tab)) do
tab := rand_array length;
done;
!tab
;;
Cette fonction prend un seul argument, la taille du tableau :
rand_array_inj 12;;
rand_array_inj 12;;
rand_array_inj 12;;
Fonction de test :
let print = Printf.printf;;
let testtri mysort cmp length nbrun () =
print "Test d'un tri, %i simulations avec des tableaux de longueur %i.\n " nbrun length;
for i = 0 to nbrun - 1 do
let t1 = rand_array length in
let t2 = Array.copy t1 in
mysort cmp t1;
Array.fast_sort cmp t2;
try assert( t1 = t2 ) with _ -> begin
print "Avec des tableaux de taille %i, le test numéro %i a échoué." length i;
Format.printf "@[t1=[|"; Array.iter (fun i -> Format.printf " %i;" i) t1; Format.printf "|]@]@ ";
Format.printf "@[t2=[|"; Array.iter (fun i -> Format.printf " %i;" i) t2; Format.printf "|]@]@ ";
end;
done;
flush_all ();
;;
La fonction de tri par défaut marche bien, évidemment.
testtri Array.sort compare 10 10 ();;
testtri tri_bulle compare 10 10 ();;
testtri tri_bulle_opt compare 10 10 ();;
Ça marche !
testtri tri_bulle compare 100 1000 ();;
Il est très semblable au tri à bulle, sauf que le tableau sera parcouru alternativement dans les deux sens.
Le tri cocktail a une complexité en $\mathcal{O}(n^2)$ dans le pire des cas et en moyenne. Il a l'avantage d'être en place.
let tri_cocktail cmp tab =
let n = Array.length tab in
let echange = ref true in
while !echange do
echange := false;
(* Parcours croissant *)
for j = 0 to n - 2 do
if cmp tab.(j + 1) tab.(j) < 0 then begin
swap tab (j + 1) j;
echange := true
end;
done;
(* Parcours decroissant *)
for j = n - 2 downto 0 do
if cmp tab.(j + 1) tab.(j) < 0 then begin
swap tab (j + 1) j;
echange := true
end;
done;
done;
;;
Il existe aussi une version plus efficace, qui diminue la taille des parcours au fur et à mesure.
let tri_cocktail_opt cmp tab =
let n = Array.length tab in
let echange = ref true in
let debut = ref 0 and fin = ref (n - 2) in
while !echange do
echange := false;
(* Parcours croissant *)
for j = !debut to !fin do
if cmp tab.(j + 1) tab.(j) < 0 then begin
swap tab (j + 1) j;
echange := true
end;
done;
fin := !fin - 1;
(* Parcours decroissant *)
for j = !fin downto !debut do
if cmp tab.(j + 1) tab.(j) < 0 then begin
swap tab (j + 1) j;
echange := true
end;
done;
debut := !debut + 1;
done;
;;
testtri tri_cocktail compare 10 10 ();;
testtri tri_cocktail_opt compare 10 10 ();;
Ça marche !
testtri tri_cocktail compare 100 1000 ();;
Avec ce morceau de code on peut facilement mesurer le temps d'exécution :
let time f =
let t = Sys.time() in
let res = f () in
Printf.printf " Temps en secondes: %fs\n" (Sys.time() -. t);
flush_all ();
res
;;
time (testtri Array.sort compare 100 10000);;
time (testtri tri_bulle compare 100 10000);;
time (testtri tri_bulle_opt compare 100 10000);;
time (testtri tri_cocktail compare 100 10000);;
time (testtri tri_cocktail_opt compare 100 10000);;
Sur de petits tableaux, les versions "optimisées" ne sont pas plus forcément plus rapides (comme toujours).
On vérifie quand même que sur des tableaux aléatoires, le tri cocktail optimisé semble le plus rapide des quatre implémentations.
Ca suffit à voir que les quatre algorithmes implémentés ici ne sont pas en temps sous quadratique.
time (testtri Array.sort compare 1000 1000);;
time (testtri tri_bulle compare 1000 1000);;
time (testtri tri_bulle_opt compare 1000 1000);;
time (testtri tri_cocktail compare 1000 1000);;
time (testtri tri_cocktail_opt compare 1000 1000);;
Les deux algorithmes ne sont pas trop difficiles à implémenter, et fonctionnent de façon très similaire.
Allez voir d'autres notebooks !