let affiche_tab = fun grille -> let n = vect_length grille in for k = 0 to (n - 1) do printf__printf "%d\n" grille.(k) done;; let rec affiche_liste liste = match liste with [] -> () | t :: q -> (printf__printf "%d\n" t; affiche_liste q);; (* Performance des tris *) (* let new_counter() = let i = ref 0 in ((fun () -> !i) , (fun () -> i := !i + 1 ), fun () -> i := 0);; let (num_comp, incr_comp, reset_comp) = new_counter();; let (num_item, incr_item, reset_item) = new_counter();; let (num_assign, incr_assign, reset_assign) = new_counter();; let reset_all() = reset_comp() ; reset_item() ; reset_assign();; let stat() = printf__sprintf "%d comparaisons, %d accès à des éléments, %d affectations" (num_comp()) (num_item()) (num_assign());; let prefix < a b = incr_comp() ; (eq__compare a b) < 0;; let vect_item v i = incr_item() ; vect__vect_item v i;; let vect_assign v i a = incr_assign() ; vect__vect_assign v i a;; 3 < 4;; let v = [| 0 |];; v.(0) <- 3;; stat();; *) (* Correction des tris *) (* let random_vect randomizer = let n = random__int 10 in vect__init_vect n (fun i -> randomizer()) ;; let random_vectvect() = random_vect (fun () -> random_vect (fun () -> random__int 10)) ;; random_vectvect() ;; let teste_tri (trieur : 'a vect -> unit) = let v = random_vectvect() in let l = vect__vect_length v in let v_trie_selon_f = vect__init_vect l (fun i -> let vi = vect__copy_vect v.(i) in trieur vi ; vi) in print_endline "Le tri selon le trieur passé en argument termine !" ; let v_trie = vect__init_vect l (fun i -> let vi = vect__copy_vect v.(i) in vect__vect_of_list (sort__sort (fun a b -> (compare a b) > 0) (vect__list_of_vect vi))) in v_trie_selon_f = v_trie ;; teste_tri (fun a -> ()) ;; *) let tri_parselection = fun table -> let n = vect_length table in let min_tab = fun i j -> let a = ref (table.(i), i) in for k = (i + 1) to j do if table.(k) < (fst !a) then a := (table.(k), k) done; !a in for k = 0 to (n - 1) do let mini = min_tab (k + 1) (n - 1) in table.(snd mini) <- table.(k); table.(k) <- (fst mini) done;; (* ////////////// *) let tri_par_insertion = fun table -> let find_position = fun tab nb -> let n = vect_length tab and cont = ref true in let i = ref n in while !i > 0 && !cont do if tab.(!i - 1) <= nb then cont := false; decr i done; !i in let n = vect_length table in let ret = make_vect (n + 1) 0 in let changer = fun indice nb maxi -> for k = maxi downto indice do ret.(k + 1) <- ret.(k) done; ret.(indice) <- nb in ret.(0) <- table.(0); for k = 1 to (n - 1) do let a = find_position (sub_vect ret 0 k) table.(k) in changer a table.(k) (k + 1) done; ret;; (*********************) let find_position = fun tab k -> let n = vect_length tab in let m = ref 0 in for i = 0 to (k - 1) do if tab.(i) <= tab.(k) then m := i + 1 done; !m;; let tri_par_insertion = fun table -> let n = vect_length table in let changer = fun indice nb maxi -> for k = (maxi - 1) downto indice do table.(k + 1) <- table.(k) done; table.(indice) <- nb in for k = 1 to (n - 1) do let a = find_position table k in changer a table.(k) k done;; (* ////////////// *) let tri_par_bulle = fun tab -> let fini = ref false in let n = vect_length tab in while not !fini do fini := true; for k = 0 to (n - 2) do let a = tab.(k) and b = tab.(k + 1) in if a > b then (fini := false; tab.(k) <- b; tab.(k + 1) <- a) done; done;; (* fin tris *) (* début dichotomie *) let trouve_dicho = fun tab elem -> let rec cherche = fun debut fin -> let milieu = (debut + fin) / 2 in if debut = fin then (elem = tab.(debut), debut) else if fin = debut + 1 then (if tab.(debut) = elem then (true, debut) else if tab.(fin) = elem then (true, fin) else (false, 0)) else (if tab.(milieu) < elem then (cherche milieu fin) else if tab.(milieu) > elem then (cherche debut milieu) else (true, milieu)) in cherche 0 ((vect_length tab) - 1);; (* diviser pour régner *) (* tri fusion *) let rec partage liste = match liste with [] -> ([], []) | t :: [] -> ([t], []) | a :: b :: q -> let z = partage q in (a :: (fst z), b :: (snd z));; let rec fusion l1 l2 = match (l1, l2) with ([], _ ) -> l2 | (_, []) -> l1 | (a :: q, b :: t) -> if a < b then (a :: (fusion q l2)) else (b :: (fusion l1 t));; let rec tri_fusion = fun liste -> match liste with [] -> [] | t :: [] -> [t] | _ -> (let (l1, l2) = partage liste in let (list1, list2) = (tri_fusion l1, tri_fusion l2) in fusion list1 list2);; (* tri rapide *) let rec partage2 liste elem = match liste with [] -> ([], []) | a :: q -> let z = (partage2 q elem) in (if a < elem then (a :: (fst z), (snd z)) else ((fst z), a :: (snd z)) );; let rec tri_rapide = fun liste -> match liste with [] -> [] | t :: [] -> [t] | t :: q :: [] -> if t < q then [t; q] else [q; t] | _ -> (let (l1, l2) = partage2 liste (hd liste) in let (list1, list2) = (tri_rapide l1, tri_rapide l2) in list1 @ list2);; (* tri rapide du tableau *) (* trier un tableau avec la méthode du pivot *) let pivoter = fun tableau debut fin -> let pivot = tableau.(debut) in let deb = ref debut and fi = ref (fin) and i = ref (debut + 1) in while !deb <= !fi && !i <= !fi do let a = tableau.(!i) in if a < pivot then (tableau.(!deb) <- a; incr deb) else let b = tableau.(!fi) in (tableau.(!fi) <- a; tableau.(!i) <- b; decr fi; decr i); incr i done; tableau.(!deb) <- pivot;; (* //////////// *) (* tri par base *) let trier = fun tab k -> let n = vect_length tab in for l = 0 to (n - 1) do done;; let rec tri_par_base = fun tabl k -> (* k : nb de chiffres *) let a = trier tabl k in (* le k_ieme chiffre *) tri_par_base tabl (k - 1);; (* /////////////// *) (* Entrée - Sortie *) let a = [ 5; 1; 3; 9; 2; 8; 19; 42; 0; 4] in (*let b = tri_fusion a in affiche_liste b; print_newline(); print_string "coucou"; print_newline(); let c = tri_fusion a in affiche_liste c;; print_newline();; print_string "coucou";; print_newline();; *) let aa = [| 5; 1; 3; 9; 2; 8; 19; 42; 0; 4 |] in pivoter aa 0 ((vect_length aa) - 1); affiche_tab aa;; (* let bb = tri_par_insertion aa in affiche_tab bb;;*) print_newline();;