(* Recherche des sqrt(n) plus grands éléments parmi n *)

(* Liste aléatoire *)
random__init (int_of_float (sys__time()));;
let rec rndlist = function
    0 -> []
  | n -> (random__int 100)::(rndlist (n-1));;

(* Calcul de l'entier immédiatement supérieur à la racine de la longueur de l *)
let rac_length l = 
  let tmp = sqrt (float_of_int (list_length l))
  in let tmp_i = int_of_float tmp
  in if (tmp >. (float_of_int tmp_i))
    then tmp_i + 1
    else tmp_i
;;

(* Algorithme naïf *)
(* On parcours l'ensemble en maintenant la liste des sqrt(n) plus grands. Complexite en n*sqrt(n) *)

(* Insertion de l'élément x dans la liste des plus grands. k contient la position dans la liste. Dès
   que k atteint la valeur 0, on jette le reste de la liste. Sinon, on insère x à sa bonne
   position. *)
let rec insert x k l = match k,l with
  | 0, _    -> []
  | k, []   -> [x]
  | k, t::q -> 
      if x >= t
      then x::(insert t (k-1) q)
      else t::(insert x (k-1) q)
;;

let racinemax l = 
  let rec aux taille result = function
    | [] -> result
    | t::q -> aux taille (insert t taille result) q
  in aux (rac_length l) [] l;;

(* Algorithme un peu moins naïf *)
(* On trie la liste par ordre décroissant et on récupère les sqrt(n) premiers. Complexité en n*ln(n)
   pour le tri. *)
let racinemax_bst l =
  let rec extract_k l k = match (l,k) with
    | [], _  -> failwith "Erreur extract_k : liste trop courte"
    | _, 0   -> []
    | t::q,k -> t::(extract_k q (k-1))
  in extract_k (sort__sort (prefix >=) l) (rac_length l)
;;

(* Amélioration de l'algorithme *)
(* si n = p², la complexité devient : 
   - recherche de maxima par ligne : p*p
   - traitement des p lignes : p*(p + p) 
D'où une complexité lineaire en n !
*)

(* Affichage d'une matrice carrée d'entiers (pour le débugage) *)
let print_matrix m t =
  for i=0 to (t-1) do
    for j=0 to (t-1) do print_int m.(i).(j); print_char ` ` done;
    print_newline();
  done
;;

(* Met le maximum de deux éléments en tête du tableau *)
let swap a i j = let tmp = a.(i) in a.(i) <- a.(j); a.(j) <- tmp;;

(* Met le maximum en tête du tableau *)
let rec cherchemax a = function
  | 0 -> ()
  | i -> 
      if a.(0) < a.(i) then swap a 0 i;
      cherchemax a (i-1)
;;

(* Transformation d'une liste de n <= p² éléments en une matrice carrée de taille p. *)
let matrix_of_list l = let p = rac_length l
in let rec aux result i = function
  | [] -> result
  | t::q -> (result.(i/p).(i mod p) <- t; aux result (i+1) q)
in aux (make_matrix p p (it_list min (hd l) (tl l))) 0 l;;

let racinemax_2 l = 
  let mtrx = matrix_of_list l and p = rac_length l
  and result = ref [] and ppl = ref 0 and pgl = ref 0
  in
    for i=0 to (p-1) do cherchemax mtrx.(i) (p-1) done;
    (* print_matrix mtrx p; print_newline(); *)
    for deb=0 to (p-1) do
      ppl := deb; pgl := deb;
      for i=deb to (p-1) do 
        if mtrx.(!ppl).(0) > mtrx.(i).(0)
        then ppl := i
        else if mtrx.(!pgl).(0) < mtrx.(i).(0)
        then pgl := i
      done;
      (* print_matrix mtrx p; print_newline(); *)
      result := mtrx.(!pgl).(0)::!result;
      mtrx.(!pgl).(0) <- mtrx.(!ppl).(0);
      cherchemax mtrx.(!pgl) (p-1);
      swap mtrx deb !ppl;
      (* print_matrix mtrx p; print_newline(); *)
    done;
    !result
;;