(* MINES - PONTS 99 *) (* Un algorithme de tri d'un tableau *) let T = [|0; 23; 12; 3; 4; 67; 10; 9; 6; 7; 12|];; type arbre = | nil | F of int | N of int * arbre * arbre ;; let construit_arbre t j = let rec aux i = if 2 * i > j then F(t.(i)) else if 2 * i = j then N(t.(i), aux j, nil) else N(t.(i), aux (2*i), aux (2*i+1)) in aux 1 ;; (* construit_arbre T 8 -> N(23, N(12, N(4, F 6, nil), F 67), N(3, F 10, F 9)) *) let echanger t i j = let x = t.(i) in t.(i) <- t.(j); t.(j) <- x ;; let rec ordonner t i j = if 2 * i = j && t.(i) < t.(j) then echanger t i j; if 2 * i < j then let (a,b,c)= (t.(i),t.(2*i),t.(2*i+1)) in if a < b then if b < c then begin echanger t (2*i+1) i; ordonner t (2*i+1) j end else begin echanger t (2*i) i; ordonner t (2*i) j end else if b < c && a < c then begin echanger t (2*i+1) i; ordonner t (2*i+1) j end ;; let ordonner_totalement t n = for j = n/2 downto 1 do ordonner t j n done ;; (* ordonner_totalement T 8;; -> [|0; 67; 23; 10; 6; 12; 3; 9; 4; 7; 12|] construit_arbre T 8;; -> N(67, N(23, N(6, F 4, nil), F 12), N(10, F 3, F 9)) *) let bulle t j = echanger t 1 j; ordonner t 1 (j-1) ;; let trier t n = ordonner_totalement t n; for j= n downto 2 do bulle t j done; t;; (* trier [|0; 5; 3; 7; 9; 1; 4; 8; 6; 2|] 9;; -> [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|] *) (* ---------------------------- FIN -----------------------------*)