let p i = i/2;;
let g i = i*2;;
let d i = i*2+1;;
let e n i = i >= 0 && i < n;;

(* QUESTION 1 ============================================================== *)

let ech a i j = 
  let t = a.(i) in
  a.(i) <- a.(j);
  a.(j) <- t
;;

(* La structure de tas représente deux propriétés:
   - La racine est plus grande que tous les éléments des sous-arbres.
   - Les sous-arbres sont des tas.

   Lorsque seule la première propriété est violée, on peut la corriger
   en remplaçant la racine par la plus grande valeur de tous ses
   sous-arbres (qui, étant des tas, l'ont à leur racine), puis en 
   corrigeant récursivement la violation de la propriété sur le
   sous-arbre où l'ancienne racine a été placée.
*)

let rec percoler t n i =
  let h = ref i in
  if e n (g i) && t.(!h) < t.(g i) then h := g i;
  if e n (d i) && t.(!h) < t.(d i) then h := d i;
  if !h <> i then (ech t i !h; percoler t n !h)
;;

(* Complexité: on descend dans le tas jusqu'à une feuille (au pire), soit
   O(log n)
*)

(* QUESTION 2 ============================================================== *)

(* On dispose d'un tableau de taille n. En appliquant la fonction de 
   percolation depuis la fin jusqu'au début, on obtient un tas complet,
   puisque l'invariant (qui est que les éléments d'indice supérieur à i sont
   des racines de tas) garanti que percoler sur l'indice i va faire de cet 
   indice une racine de tas).
*)

let transformer_en_tas t =
  for i = vect_length t - 1 downto 0 do
    percoler t (vect_length t) i
  done
;;

(* Pour transformer en tas, on effectue n fois l'opération de percolation, soit
   O(n log n)
*)

(* QUESTION 3 =============================================================== *)

(* On supprime le plus grand élément du tas, en le remplaçant par l'élément
   de plus grand indice. Cela viole la première propriété du tas entier,
   que l'on corrige par percolation. On recommence jusqu'à avoir vidé le
   tas. 
*)

let trier_tas t =
  for i = vect_length t - 1 downto 1 do
    ech t 0 i;
    percoler t i 0
  done
;;

(* On effectue n fois un échange et une percolation, soit O(n log n) *)

let tri_par_tas t =
  transformer_en_tas t;
  trier_tas t
;;

(* Complexité totale O(n log n) *)

(* QUESTION 4 ============================================================== *)

let rec couper i = function
  | [] -> [], []
  | t::q -> 
      let g, d = couper i q in
      if t land (1 lsl i) = 0 then 
        t :: g, d
      else
        g, t :: d
;;

(* QUESTION 5 ============================================================== *)

let rec couper_deux l i = function
  | [] -> couper i l
  | t::q ->    
      let g, d = couper_deux l i q in
      if t land (1 lsl i) = 0 then 
        t :: g, d
      else
        g, t :: d
;;

(* QUESTION 6 ============================================================== *)

(* Supposons que les nombres soient triés modulo 2^k. On coupe alors la liste
   en, d'un côté, les nombres qui ont un "1" en position k, et ceux qui ont
   un "0". Cela revient à séparer les nombres suivant leur position par
   rapport à 2^k, modulo 2^{k+1}. L'ordre des deux listes est conservé, donc
   elles sont toujours triées modulo 2^k. Au final, la liste recollée est
   donc triée modulo 2^{k+1}.
*)

let tri_par_base l = 
  let inf, sup = ref [], ref l in
  for k = 0 to 31 do
    (* Trié modulo 2^k => on trie modulo 2^{k+1} *)
    let g, d = couper_deux !sup k !inf in
    inf := g;
    sup := d;
  done;
  !inf @ !sup
;;

tri_par_base [ 18; 3; 11; 27; 1; 6 ];;
 
(* Complexité: chaque découpage est en temps O(n). Si M est le plus grand
   entier représentable, alors la boucle se répère log2 M fois, et donc la
   complexité totale est O(n log M)
*)

(* QUESTION 7 ============================================================== *)

(* On travaille suivant le même principe: en triant les mots suivant leur
   k dernières letters, on peut les trier suivant leur k+1 dernières lettres
   en les classant suivant leur k+1-ème lettre depuis la fin (dans autant de
   listes qu'il y a de lettres dans l'alphabet). Cette opération prend un
   temps O(n) et doit être répété une fois pour chaque lettre du mot. La
   complexité totale du tri est donc O(mn).

   Dans le pire cas, la comparaison de deux chaînes prend un temps O(m), 
   et donc dans un algorithme par comparaison, qui réalise O(n log n) 
   comparaisons, le nombre total de comparaisons de caractères sera
   O(m n log n). C'est plus long que la version par bases.

   En pratique, la comparaison de deux chaînes s'arrête lorsque deux lettres
   sont différentes. Supposons des mots infinis. Quel sera le nombre moyen
   de comparaisons? Si ce nombre est M, et que la probabilité que deux
   lettres soient égales est p, alors:

   M =      (1 - p)           +        (1 + M) p
            \-----/                    \-------/
    Si 1è lettre est diff.       Si 1è lettre identique.

   Et donc M = 1 / (1 - p). 

   => Pour des mots aléatoires sur l'alphabet latin, p = 1/26 et donc M = 1.04,
      ce qui rend un tri en O(M n log n) meilleur qu'un tri en O(mn).

   => Pour des mots aléatoires sur le génome, p = 1/4, M = 1.3, ce qui
      là encore est très faible.

   Question subsidiaire: trouver l'erreur dans ce raisonnement.
*)