Info_MPSI/MP/concours/tri.ml

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

let rec tri_insertion l = match l with
| [] -> []
| t::q -> insere t (tri_insertion q)
;;

(*Tri par insertion sur des tableaux*)
let insere_t i t = let k = ref (i-1) and aux = t.(i) in
  while (!k >= 0) && (t.(!k)> aux) do
    t.(!k+1)<- t.(!k);
    k:= !k +1
  done;
  t.(!k+1) <- aux
;;

let tri_insertion_t t = let n = Array.length t in
  for i = 1 to n do
  insere_t i t
  done;
  t
;;

(*Tri par selection sur des tableaux*)
let rec echange i j a = let aux = a.(i) in
 a.(i)<- a.(j);
 a.(j)<-aux
;;
let minimum t i = let m = ref i in
  for j= i+1 to Array.length t do
    if t.(j)< !m then m:= j
    done;
    !m
;;
let tri_selection t = let n = Array.length t in
  for i = 0 to n-2 do
    echange (minimum t i) i t
  done;
  t
;;
(*Tri par selection sur des listes*)
let rec minimum_et_reste l = match l with
| [] -> failwith "Pas d'élément dans la liste"
| [a] -> a,[]
| t::q -> let (m,r) = minimum_et_reste q in
  if m<t then (m, t::r)
  else (t,q)
;;

let rec tri_selection_l l = match l with
| [] -> []
| _ -> let (m,r) = minimum_et_reste l in
  m::(tri_selection_l r)
;;
(*Tri à bulles sur des tableaux*)
let rec une_etape t i = let n = Array.length t and b = ref false in
  for k = n-1 downto i+1 do
    if (t.(k)< t.(k-1)) then
      begin
        echange k (k-1) t;
        b:= true
      end
    done;
    !b
;;
let tri_bulles t = let i = ref 0 in
  while (une_etape t !i) do
    i := !i + 1
  done;
  t
;;
(*Tri à bulles sur des listes*)
let rec une_etape_l l = match l with
| [] -> false,l
| t::q -> let b,t1::q1 = une_etape_l q in
  if (t<= t1) then b, t::t1::q
  else true,t1::t::q
;;

let rec tri_bulles_l l = match l with
| [] -> []
| _ -> let b,t::q = une_etape_l l in
  if b then t::(tri_bulles_l q)
  else l
;;
(*Tri fusion pour des listes*)
let rec partition l = match l with
| [] -> ([],[])
| [x] -> ([x],[])
| t1::t2::q -> let q1,q2 = partition q in (t1::q1,t2::q2)
;;

let rec fusion l1 l2 = match (l1,l2) with
| [],[] -> []
| [],l2 -> l2
| l1,[] -> l1
| t1::q1,t2::q2 -> if t1 <= t2 then t1::(fusion q1 l2)
  else t2::(fusion l1 q2)
;;
let rec tri_fusion l = match l with
| [] -> []
| [x] -> [x]
| _ -> let l1,l2 = partition l in
  fusion (tri_fusion l1) (tri_fusion l2)
;;
(*Tri fusion pour les tableaux*)
let fusion_t t l m u =
  let aux = Array.make (u-l + 1) t.(0) and i = ref l and j = ref (m+1) and k = ref 0 in
  while (!i<= m) && (!j <= u) do
    if (t.(!i)<= t.(!j)) then
      begin
        aux.(!k) <- t.(!i);
        i:= !i + 1
      end
    else
      begin
        aux.(!k) <- t.(!j);
        j := !j +1
      end;
      k:= !k + 1
    done;
    while (!i <= m) do
      aux.(!k) <- t.(!i);
      i:= !i +1;
      k:= !k + 1
    done;
    while (!j <= u) do
      aux.(!k) <- t.(!j);
      j:= !j + 1;
      k := !k +1
    done;
    for x=0 to (!k-1) do
      t.(l+x) <- aux.(x)
    done
;;

let tri_fusion_t t =
  let rec tri_fuion_aux t l u =
    if (l<u) then
      begin
        let m = (l+u)/2 in
          tri_fuion_aux t l m;
          tri_fuion_aux t (m+1) u;
          fusion_t t l m u;
      end;
    in tri_fuion_aux t 0 (Array.length t -1 )
;;

(*Tri rapide pour les tableaux*)

let partition_rapide t d f =
  let p = t.(d) and i = ref d in
    for j = d+1 to f do
      if t.(j) <= p then
        begin
          i := !i + 1;
          echange !i j t
        end
      done;
      echange d !i t;
      !i
;;

let tri_rapide t =
  let rec aux t d f =
    if f > d then
      begin
        let m = partition_rapide t d f in
          aux t d (m-1);
          aux t (m+1) f
      end
    in
    aux t 0 (Array.length t -1)
;;