(* ===================================================== *)
(*      Apprentissage de la programmation avec OCaml     *)
(*      Catherine Dubois & Valérie Ménissier-Morain      *)
(*                Éditions Hermès Sciences               *)
(*                        Mars 2004                      *)
(* ===================================================== *)
(* Fichier MLSRC/Tris_listes/test_insertion_liste.ml     *)
(* ===================================================== *)

open Unix;;
open Insertion_liste;;

(* Les fonctions de génération de liste *)
(* n -> 1 *)
let rec ordre_décroissant n =
  if n =1 then [1] else n::(ordre_décroissant (n-1));;

(* 1 -> n *)
let ordre_croissant n = List.rev (ordre_décroissant n);;

let épi n =
  let rec épi_rec d f =
    if d < f then d::f::(épi_rec (d+1) (f-1)) else [d] in
  épi_rec 1 n;;

let rec aléatoire n = if n = 0 then [] else (Random.int n)::(aléatoire (n-1));;

(* Les fonctions de test *)
let tri_liste_triée n nb =
  let l = (ordre_croissant n) in
  let t1 = Unix.times () in
  for i = 1 to nb do tri_insertion l; done;
  let t2 = Unix.times () in
  Printf.printf "  déjà triée par ordre croissant: %.4f secondes\n"
    ((t2.tms_utime -. t1.tms_utime)/.(float_of_int nb));;

let tri_liste_en_épi n =
  let l = (épi n) in
  let t1 = Unix.times () in
  tri_insertion l;
  let t2 = Unix.times () in
  Printf.printf "  en épi                        : %.4f secondes\n"
    (t2.tms_utime -. t1.tms_utime);;

let test_insertion_aleatoire n nb =
  let t1 = Unix.times () in
  for i = 1 to nb do
    let l = (aléatoire n) in
    tri_insertion l;
  done;
  let t2 = Unix.times () in
  Printf.printf "  aléatoire moyennée            : %.4f secondes\n"
    ((t2.tms_utime -. t1.tms_utime)/.(float_of_int nb));;

let tri_liste_triée_ordre_inverse n =
  let l = (ordre_décroissant n) in
  let t1 = Unix.times () in
  tri_insertion l;
  let t2 = Unix.times () in
  Printf.printf "  triée par ordre décroissant   : %.4f secondes\n"
    (t2.tms_utime -. t1.tms_utime);;

(* Les tests *)
print_endline "Liste de 10000 éléments";
tri_liste_triée 10000 10000;
tri_liste_en_épi 10000;
test_insertion_aleatoire 10000 10;
tri_liste_triée_ordre_inverse 10000;;

print_endline "\nListe de 20000 éléments";
tri_liste_triée 20000 1000;
tri_liste_en_épi 20000;
test_insertion_aleatoire 20000 10;
tri_liste_triée_ordre_inverse 20000;;

print_endline "\nListe de 40000 éléments";
tri_liste_triée 40000 100;
tri_liste_en_épi 40000;
test_insertion_aleatoire 40000 10;
tri_liste_triée_ordre_inverse 40000;;
Ce document a été traduit de LATEX par HEVEA.