let insere i t = 
  let j = ref i in
    while !j> 0 && t.(!j)<t.(!j-1) do
      let aux = t.(!j) in
        t.(!j)<- t.(!j-1);
        t.(!j-1)<-aux;
        j := !j - 1
    done;
;;

let tri_insertion t =
  let n = Array.length t in
    for i = 1 to n-1 do
    insere i t
    done;
    t
;;

let rec minimum_reste l = match l with
| [x] -> x, []
| t1::q -> let (m,r) = minimum_reste q in
  if t1<m then (t1,m::r)
  else (m,t1::r);;

let rec tri_selection l = match l with
| [x] -> [x]
| _ -> let (aux1,aux2) = minimum_reste(l) in
  aux1::tri_selection aux2
;;

let rec une_etape l = match l with
| [x] -> false,[x]
| t::q -> let b, t1::q1 = une_etape q in
  if t1>t then b, t::t1::q1

  else true, t1::t::q1;;

let rec tri_bulles l = match l with 
| [] -> []
| _ -> let b,t::q = une_etape l in
  if b then t::(tri_bulles q)
  else l
;;


let echange t i j = let aux = t.(i) in
  t.(i)<-t.(j);
  t.(j)<-aux
;;
let retourne_tableaux t i=
  for j=0 to i/2 do
    echange t j (i-j)
  done;
;;

let maximum_tableaux t i = let k = ref 0 in
  for j = 0 to i do
    if t.(j) > t.(!k) then k:= j
    done;
  !k
;;

let tri_pancake_tableaux t = let n = Array.length t in
  for i = (n-1) downto 1 do
    let aux = maximum_tableaux t i in 
    retourne_tableaux t aux;
    retourne_tableaux t i
  done;
  t
;;