(* I Maximum d'un tableau par méthode diviser pour régner
Etape de division : on coupe le tableau en deux le maximum de chaque moitié pour avoir le maximum. Il faudra faire attention dans les appels récursifs à ce qu'une moitié ne soit pas vide ! *)

let max_tab_DPR (tab : 'a array) : 'a =
  let rec max_tab_DPR_aux deb fin =
    if fin = deb then tab.(deb)
    else let m = (fin + deb) / 2  in
         max (max_tab_DPR_aux (m + 1) fin) (max_tab_DPR_aux deb m)
  in max_tab_DPR_aux 0 (Array.length tab - 1)
;;

max_tab_DPR [|3|];;
max_tab_DPR [|3; 4|];;
max_tab_DPR [|3; 5; 4|];;
max_tab_DPR [|3; 5; 4; 2|];;
max_tab_DPR [|3; 5; 4; 7; 6|];;    
max_tab_DPR [|3; 1; 5; 2; 7; 3; 1; 6|];;
max_tab_DPR [|3; 1; 7; 2; 8; 3; 1; 6; 3; 5; 1; 3; 6; 6|];;

(* Version en laissant plus clairement les calculs d'indices *)
let max_tab_DPR2 (tab : 'a array) : 'a =
  let rec max_tab_DPR_aux deb fin =
    if fin = deb then tab.(deb)
    else let m = (fin + 1 - deb) / 2  in
         max (max_tab_DPR_aux (deb + m) fin) (max_tab_DPR_aux deb (deb + m - 1))
  in max_tab_DPR_aux 0 (Array.length tab - 1);;

max_tab_DPR2 [|3|];;
max_tab_DPR2 [|3; 4|];;
max_tab_DPR2 [|3; 5; 4|];;
max_tab_DPR2 [|3; 5; 4; 2|];;
max_tab_DPR2 [|3; 5; 4; 7; 6|];;    
max_tab_DPR2 [|3; 1; 5; 2; 7; 3; 1; 6|];;
max_tab_DPR2 [|3; 1; 7; 2; 8; 3; 1; 6; 3; 5; 1; 3; 6; 6|];;
  
(* Pour ce qui est de la complexité la relation de récurrence est C(n) = 2C(n/2) + a. Avec la technique habituelle on montre que la complexité est en O(n). On n'a bien sûr rien gagné en utilisant la méthode DPR. Mais ici c'est normal car de toutes façons il faut forcément avoir examiné tous les éléments pour être sûr d'avoir trouvé le maximum, ce qui nécessite une complexité minimale en O(n) qu'on atteint déjà par un parcours itératif exhaustif de tous les élements *)

(* II Racine carré entière *)  
(* On peut écrire une fonction sq pour calculer le carré d'un entier pour alléger le code *)
let sq (n : int) : int = n * n ;;

let racine (n : int) : int =
  let i = ref 0 in
  while sq !i <= n do
    incr i
  done ;
  !i - 1 ;;

(* La complexité est évidemment en O(sqrt(n)) *)

racine 2499 ;;
racine 2500 ;;
racine 2501 ;;

(* Pour la méthode DPR l'idée est de diviser à chaque appel récursif l'intervalle d'entiers dans lequel se trouve la réponse cherchée. Il faut donc gérer deux entiers qui sont les bornes de cet intervalle *)  
(* Version impérative de la méthode DPR. Il faut faire attention à l'appel avec 1, car alors a = 0 b = 1 rep = 0 on rentre donc la boucle while
qui en sortie va donne a = 0, b = 1 inchangée et rep = 0 et on boucle indéfiniment  *)  
let racineDPRi (n : int) : int =
  if n <= 1 then n else
    let a = ref 0 and b = ref n in
    let  rep = ref ((!a + !b) / 2) in
    while not (sq !rep <= n && sq (!rep + 1) > n) do
      if sq !rep > n then
        b := !rep
      else 
        a := !rep ;
      rep := ((!a + !b ) / 2)
    done ;
    !rep ;;

racineDPRi 0 ;;
racineDPRi 1 ;;
racineDPRi 2 ;;
racineDPRi 3 ;;
racineDPRi 4 ;;
racineDPRi 5 ;;      
racineDPRi 2499 ;;
racineDPRi 2500 ;;
racineDPRi 2501 ;;      
racineDPRi 100000 ;;

(* Solution astucieuse : augmenter l'intervalle de départ pour éviter d'être bloqué pour le cas n = 1 !*)  
let racineDPRi2 (n : int) : int =
  let a = ref 0 and b = ref (n + 1) in
  let  rep = ref ((!a + !b) / 2) in
  while not (sq !rep <= n && sq (!rep + 1) > n) do
    if sq !rep > n then
      b := !rep
    else 
      a := !rep ;
    rep := ((!a + !b ) / 2)
  done ;
  !rep ;;
  
racineDPRi2 0 ;;
racineDPRi2 1 ;;
racineDPRi2 2 ;;
racineDPRi2 3 ;;
racineDPRi2 4 ;;
racineDPRi2 5 ;;      
racineDPRi2 2499 ;;
racineDPRi2 2500 ;;
racineDPRi2 2501 ;;      
racineDPRi2 100000 ;;
 
(* Version récursive *)
(* Là aussi il faut faire attention au cas n = 1 *)  
let racineDPRr n =
  let rec racineDPRaux a b =
    let mil = (a + b) / 2 in
      if mil * mil > n then racineDPRaux a mil 
      else if (mil + 1) * (mil + 1) <= n then racineDPRaux mil b 
      else mil 
  in if n <= 1 then n else racineDPRaux 0 n ;;

racineDPRr 0 ;;
racineDPRr 1 ;;
racineDPRr 2 ;;
racineDPRr 3 ;;
racineDPRr 4 ;;
racineDPRr 5 ;;      
racineDPRr 2499 ;;
racineDPRr 2500 ;;
racineDPRr 2501 ;;      
racineDPRr 100000 ;;
  
(* Autre possibilité : les paramètres de la fonction auxiliaires forme un encadrement a, b de la valeur cherchée tel que la valeur cherchée appartient à [a, b[, avec b > a. Le cas de base est celui où b = a + 1, et dans ce cas on rend a. L'appel initial se fera avec 0 n, ce qui suppose que n > 1. Mais il y a un piège si n = 1, car il faut rendre 1 dans ce cas... D'où la proposition de code suivante : *)
let racineDPRr2 n = 
  let rec racineDPRaux a b =
    if b = a + 1 then a
    else let mil = (a + b) / 2 in
      if mil * mil > n then racineDPRaux a mil 
      else racineDPRaux mil b 
     in if n <= 1 then n else racineDPRaux 0 n ;;

racineDPRr2 0 ;;
racineDPRr2 1 ;;
racineDPRr2 2 ;;
racineDPRr2 3 ;;
racineDPRr2 4 ;;
racineDPRr2 5 ;;      
racineDPRr2 2499 ;;
racineDPRr2 2500 ;;
racineDPRr2 2501 ;;      
racineDPRr2 100000 ;;
    
(* La relation de récurrence est de la forme C(n) = C(n/2) + a, ce qui montre que la complexité est logarithmique. C'est normal, c'est en fait une recherche dichotomique... *)
  
(* III Fonction swap très souvent utile pour le tri des tableaux en place *)
let nb_swaps = ref 0 ;; (* Référence pour compter le nombre d'appel à swap *)

let swap (tab : 'a array) (i : int) (j : int) : unit =
  let inter = tab.(i) in
  tab.(i) <- tab.(j) ;  
  tab.(j) <- inter ;
  incr nb_swaps ;;

(* Le principe de la fonction suivante n'est pas trouvable facilement seul dans son coin. Allez faire un tour sur wikipedia pour les explications . Faites tourner l'algo à la main pour comprendre comment cela marche *)  
let pivot (tab : 'a array) (deb : int) (fin : int) : int  =
  swap tab deb fin ; (* on met le premier élément, qui est le pivot, à la fin *)
  let j = ref deb in (* j est l'indice de la position courante telle que pour tout i < j tab.(i) < pivot *)
  for i = deb to fin - 1 do
    if tab.(i) <= tab.(fin) then
      begin
        swap tab i !j ;
        incr j
      end ;  
  done ;
  swap tab !j fin ; (* On remet le pivot à sa place *)
  !j ;; (* on rend la position du pivot *) 

(* Quelques exemples *)  
let tabtest = [|1; 3; 6; 2; 11; 10; 5; 9; 6; 4; 8; 7|] ;;
pivot tabtest 0 11 ;;
tabtest ;;
pivot tabtest 1 11 ;;
tabtest ;;
let tabtest = [|1; 3; 6; 2; 11; 2; 5; 9; 6; 4; 8; 7|] ;;
tabtest ;;
pivot tabtest 1 11 ;;
tabtest ;;
let tabtest = [|10; 9; 8; 7; 6; 5; 4; 3; 2; 1|] ;;
tabtest ;;
pivot tabtest 0 9 ;;
tabtest ;;

let tabtest = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|] ;;
tabtest ;;
pivot tabtest 2 9 ;;
tabtest ;;
  
let nb_appels = ref 0 ;; (* Variable globale pour compter le nombre d'appels récursifs *)

  
let trirapide (tab : 'a array) : 'a =
  let n = Array.length tab in
  let rec trirapideaux i j =
    incr nb_appels ;
    if j - i > 1 then
      let pospivot = pivot tab i j in
      trirapideaux i (pospivot - 1) ;
      trirapideaux (pospivot + 1) j
  in trirapideaux 0 (n - 1) ;;

nb_appels := 0 ; nb_swaps := 0 ;;    
trirapide tabtest ;;
tabtest ;;
!nb_appel ;;
!nb_swaps ;;
    
let tabtest = [|1; 7; 5; 3; 0; 3; -6; 3; 4; 1; 2; 5; 2; 3; 1; 4|] ;; 
nb_appels := 0 ; nb_swaps := 0 ;;    
trirapide tabtest ;;
tabtest ;;
!nb_appel ;;
!nb_swaps ;;

let tabtest = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|] ;; 
nb_appels := 0 ; nb_swaps := 0 ;;    
trirapide tabtest ;;
tabtest ;;
!nb_appel ;;
!nb_swaps ;;

let tabtest = [|10; 9; 8; 7; 6; 5; 4; 3; 2; 1|] ;; 
nb_appels := 0 ; nb_swaps := 0 ;;    
trirapide tabtest ;;
tabtest ;;
!nb_appel ;;
!nb_swaps ;;

(* IV Très difficile...*)  
let inversion_naif tab =
  let rep = ref [] in (* On crée une référence sur une liste que l'on va faire grossir au cours de la détection de nouvelles inversions. On pourrait se contenter d'un compteur car on s'intéresse simplement aux nombres des inversions *)
  let n = Array.length tab in
  for i = 0 to (n - 2) do
    for j = i + 1 to (n - 1) do
      if tab.(i) > tab.(j) then
        rep := (i + 1, j + 1) :: !rep (* On rajoute 1 à chaque indice pour coller aux notations de l'énoncé : x_1....x_n, et non pas x_0...x_{n-1} *)
    done
  done ;
  List.rev !rep ;;
    
inversion_naif [|2; 3; 1; 5; 4|] ;;