Option info - Tris sur liste/tableau [entier]

(* Tri par pivot sur des listes *)

(* Première version *)
let partition k l =
let rec aux_partition l l1 l2 = match l with
|[] -> (l1,l2)
|h::t when h<k -> aux_partition t (h::l1) l2
|h::t -> aux_partition t l1 (h::l2)
in aux_partition l [] [];;

(* Deuxième version *)
let rec partition a l = match l with
|[] -> ([],[])
|h::t when h>a -> let (l1,l2) = (partition a t) in (l1,h::l2)
|h::t -> let (l1,l2) = (partition a t) in (h::l1,l2);;


let rec tri_pivot l = match l with
|[] -> []
|h::t -> let (l1,l2) = partition h t in (tri_pivot l1)@[h]@(tri_pivot l2);;


(*Tri par pivot sur des tableaux*)

(* Fonction partition avec le 1er élément comme "pivot"*)
(* Description de l'algorithme :
On regarde [|5;2;6;9|]
On compare à chaque fois 5 et l'élément après.
Si l'élément est plus petit, alors on permute les deux, et on update "début" pour qu'il reste à la position de 5
Si l'élément est plus grand, on échange ce "plus grand élément" avec le dernier, et on fini plus tôt.*)
let partition t a b =
    let debut = ref a in
    let fin = ref b in
    while !debut <> !fin do
        let (ta,tb) = (t.(!debut),t.(!debut +1)) in
        if ta > tb then

        begin
        t.(!debut) <- tb;
        t.(!debut +1) <- ta;
        incr debut;
        end

        else

        begin
        t.(!debut + 1) <- t.(!fin);
        t.(!fin) <- tb;
        decr fin;
        end

        done;
        !debut;;
(* nb : "!debut" renvoyé est la position du pivot dans le tableau *)


(* Pour le tri par pivot, on va trier récursivement entre "debut et pivot" ; "pivot et fin" *)
let tri_par_pivot t =
let n = Array.length t - 1 in
    let rec aux a b =
        if a<b then
            begin
            let p = partition t a b in
            aux a (p-1);
            aux (p+1) b;
            end in
    aux 0 n;
    t;;


(* Tri par fusion sur des listes *)
let rec division l = match l with
|[] -> [],[]
|[h] -> [h],[]
|h1::h2::t -> let (l1,l2) = division t in h1::l1,h2::l2;;

let rec fusion l1 l2 = match l1,l2 with
|[],_ -> l2
|_,[] -> l1
|h1::t1,h2::t2 when h1 < h2 -> h1::(fusion t1 l2)
|h1::t1,h2::t2 -> h2::(fusion l1 t2);;

let rec tri_fusion l = match l with
|[] -> []
|[a] -> [a]
|h::t -> let (l1,l2) = division l in
            fusion (tri_fusion l1) (tri_fusion l2);;


(* Tri par insertion sur des listes *)
let rec insere a l = match l with
|[] -> [a]
|h::t when h<a -> h::(insere a t)
|h::t -> a::t;;

let tri_insertion l =
let rec aux l1 l2 = match l1 with
|[] -> l2
|h::t -> aux t (insere h l2)
in aux l [];;


(* Tri par insertion sur des tableaux *)
let array_insertion t =
let j = ref 0 in
let permute a b =
    let ta = t.(a) and tb = t.(b) in
    t.(b) <- ta;
    t.(a) <- tb in

(* On essaie d'insérer t.(i) à sa place, dans le tableau "t.(0),...,t.(i)"
Pour cela, on décale les éléments qui sont plus grand que i vers la droite *)
for i=1 to ((Array.length t)-1) do
    j:= 0 ;
    while (!j < i)&& t.(i - !j)  < t.(i - !j -1) do
        permute (i - !j) (i-1 - !j);
        incr j;
done;
t;;




(* Deuxième tri par insertion sur des tableaux *)
let array_selection t=
let n = Array.length t in
for i = 1 to n-1 do
let a = t.(i) in
let j = ref (i-1) in
    while (!j >= 0) && t.(!j) > a do
    t.(!j + 1) <- t.(!j);
    decr j;
    done;
    t.(!j + 1) <- a
    done;
    t;;



(* Tri par selection sur des listes *)
let sortir_le_max l =
let rec aux_sortir_max a l = match l with
|[] -> (a,[])
|h::t when a>h -> let (max,l_sans_max) = aux_sortir_max a t in (max,h::l_sans_max)
|h::t -> let (max,l_sans_max) = aux_sortir_max h t in (max,a::l_sans_max)
in aux_sortir_max (List.hd l) (List.tl l);;


let tri_par_selection l =
let rec aux_tri l1 l2 = match l1 with
|[] -> l2
|h::t -> let (max,l_sans_max) = sortir_le_max l1 in aux_tri l_sans_max (max::l2)
in aux_tri l [];;


(* Tri par selection sur les tableaux *)
let array_selection t =

(* Fonction qui détecte le max *)
let n = Array.length t in
for i=0 to (n-1) do
let m = ref 0 in
for j=0 to (n-i-1) do
if t.(j) > t.(!m) then m:=j ;
done ;

(* Fonction qui permute le "dernier" élément et le max *)
let (u,v) = ( t.(n-i-1), t.(!m) ) in
t.(n-i-1) <- v;
t.(!m) <- u;
done;
t;;



(* Tri à bulles sur tableau *)
(* Echange les éléments consécutifs qui ne sont pas dans le bon ordre *)
(* Recommence les procédés sur les (n-1) premiers éléments *)
let bubble_sort t =
let n = Array.length t in
for j=n-1 downto 0 do

for i=0 to j-1 do
if t.(i)>t.(i+1) then
let (u1,u2) = (t.(i),t.(i+1)) in
t.(i) <- u2;
t.(i+1) <- u1;
done;

done;
t;;