let echanger t i j =
        let k = t.(i) in
        t.(i) <- t.(j);
        t.(j) <- k;
;;


let tri_bulle ineq t =
        let n = vect_length t in
        for i = 1 to n-1 do
        for j = 1 to n-i do
                if ineq t.(j) t.(j-1) then echanger t j (j-1);
        done;
        done;
;;

let tri_bulle_c = tri_bulle (prefix <) ;;
let tri_bulle_d = tri_bulle (prefix >) ;;


let tri_selection ineq t =
        let n = vect_length t in
        for i = 0 to n-2 do
                let m = ref i in
                for j = i+1 to n-1 do
                        if ineq t.(j) t.(!m) then m:= j;
                done;
        echanger t i !m;
        done;
;;

let tri_selection_c = tri_selection (prefix <) ;;
let tri_selection_d = tri_selection (prefix >) ;;


let rec tri_insertion ineq l =

        let rec insere a = fun
                | [] -> [a]
                | (b::q) when ineq a b -> a::b::q
                | (b::q) -> b::(insere a q)
        in

        match l with
                | [] -> []
                | (a::q) -> insere a (tri_insertion ineq q)
;;

let tri_insertion_c = tri_insertion (prefix <) ;;
let tri_insertion_d = tri_insertion (prefix >) ;;


let rec tri_fusion ineq l =

        let rec coupe = fun
                | [] -> [],[]
                | (a::q) -> let (u,v) = coupe q in
                            (a::v),u
        in

        let rec fusion = fun
                | [] l -> l
                | l [] -> l
                | (a::q) (b::r) when ineq a b -> a::(fusion q (b::r))
                | l (b::r) -> b::(fusion l r)
        in

        match l with
                | []  -> []
                | [a] -> [a]
                | l   -> let (u,v) = coupe l in
                         let uu = tri_fusion ineq u and vv = tri_fusion ineq v in
                         fusion uu vv
;;

let tri_fusion_c = tri_fusion (prefix <) ;;
let tri_fusion_d = tri_fusion (prefix >) ;;


let rec quick_sort ineq l =
        let rec coupe p = fun
                | [] -> [],[]
                | (a::q) -> let u,v = coupe p q in
                            if ineq a p then (a::u),v else u,(a::v)
        in
        match l with
                |  [] -> []
                | [a] -> [a]
                | (a::q) -> let u,v = coupe a q in
                            let uu = quick_sort ineq u and vv = quick_sort ineq v in
                            uu@(a::vv)
;;

let quick_sort_c = quick_sort (prefix <) ;;
let quick_sort_d = quick_sort (prefix >) ;;


type 'a arbre = vide | N of 'a arbre * 'a * 'a arbre ;;

let tri_arbre ineq l =

        let rec ins_rech a = function
                | vide -> N(vide,a,vide)
                | N(g,n,d) when ineq a n -> N(ins_rech a g,n,d)
                | N(g,n,d) -> N(g,n,ins_rech a d)
        in

        let rec rech_of_list = fun
                | [] -> vide
                | (a::q) -> ins_rech a (rech_of_list q)
        in

        let rec list_of_rech = function
                | vide -> []
                | N(g,n,d) -> (list_of_rech g)@(n::list_of_rech d)
        in

        list_of_rech (rech_of_list l)
;;

let tri_arbre_c = tri_arbre (prefix <) ;;
let tri_arbre_d = tri_arbre (prefix >) ;;


let tri_fusion_vect ineq t =

        let fusion inf m sup =
                let n = sup-inf+1 in
                let tt = make_vect n t.(inf)
                and i = ref 0 and b1 = ref inf and b2 = ref (m+1) in
                while (!b1 <= m) && (!b2 <= sup) do
                        if ineq t.(!b1) t.(!b2) then (
                                tt.(!i) <- t.(!b1);
                                incr b1;
                        ) else (
                                tt.(!i) <- t.(!b2);
                                incr b2;
                        );
                        incr i;
                done;
                if !b1 > m then (
                        for j = !b2 to sup do
                                tt.(!i - !b2 + j) <- t.(j);
                        done;
                ) else (
                        for j = !b1 to m do
                                tt.(!i - !b1 + j) <- t.(j);
                        done;
                );
                for i = 0 to n-1 do t.(inf+i) <- tt.(i) done;
        in

        let rec trier inf sup =
                if inf < sup then (
                        let m = (inf + sup)/2 in
                        trier inf m;
                        trier (m+1) sup;
                        fusion inf m sup;
                );
        in

        trier 0 (vect_length t - 1);
;;

let tri_fusion_vect_c = tri_fusion_vect (prefix <) ;;
let tri_fusion_vect_d = tri_fusion_vect (prefix >) ;;


let tri_tas ineq t =

	let rec entasser n i =
		let g = 2*i+1 and d = 2*i+2 in
		let max = if g < n && ineq t.(i) t.(g) then g else i in
		let max = if d < n && ineq t.(max) t.(d) then d else max in
		if max <> i then (
			echanger t i max;
			entasser n max;
		);
	in

	let n = vect_length t in

	for i = n /2 -1 downto 0 do
		entasser n i;
	done;

	for i = n-1 downto 1 do
		echanger t i 0;
		entasser i 0;
	done;
;;

let tri_tas_c = tri_tas (prefix <) ;;
let tri_tas_d = tri_tas (prefix >) ;;


(* ineq doit être une inégalité stricte *)

let tri_rapide ineq t =

        let ioe a b = ineq a b || a = b in

        let placer inf sup =
	        let n = t.(sup) and
                bi = ref inf and bs = ref (sup-1) in
	        while (!bi < !bs) do
		        while ((!bi < sup) && (ioe t.(!bi) n)) do incr bi done;
        		while ((!bs > inf) && (ioe n t.(!bs))) do decr bs done;
	        	if (!bi < !bs) then (
		        	echanger t !bi !bs;
			        incr bi;
        			decr bs;
	        	);
        	done;
	        if (ineq t.(!bi) n) then incr bi;
        	if (!bi < sup) then echanger t !bi sup;
	        !bi;
        in

        let rec trier inf sup =
	        if (inf < sup) then (
		        let r = placer inf sup in
        		trier inf (r-1);
	        	trier (r+1) sup;
        	);
        in

        trier 0 ((vect_length t) -1);
;;

let tri_rapide_c = tri_rapide (prefix <) ;;
let tri_rapide_d = tri_rapide (prefix >) ;;

(* avec k un majorant strict de t, tableau d'entiers *)

let tri_denombrement t k =
        let n = vect_length t in
        let c = make_vect k 0 in
        for i = 0 to n-1 do
                let p = t.(i) in
                c.(p) <- c.(p) + 1;
        done;
        for i = 1 to k-1 do c.(i) <- c.(i) + c.(i-1) done;
        let tt = make_vect n 0 in
        for i = n-1 downto 0 do
                let p = t.(i) in
                tt.(c.(p)-1) <- p;
                c.(p) <- c.(p) - 1;
        done;
        tt;
;;