(** Le k-ième en O(n) selon AHU, p 291**) open List;; (* Pour N<75, on a besoin de Mergesort *) let rec fusion l1 l2 = match (l1,l2) with |[],_ -> l2 |_,[] -> l1 |t1::q1,t2::q2 -> if t1([],[]) |[a]->([a],[]) |(a::b::z) -> let (u,v)= egrem z in (a::u,b::v) ;; let rec mergesort= function | [] -> [] | [a] -> [a] | liste -> let (x,y)=egrem liste in fusion (mergesort x) (mergesort y) ;; (* Mergesort [2;5;8;9;1;0;6];; *) let rec k_ième k = function |[] -> failwith "liste trop courte" |t::q -> if k=1 then t else k_ième (k-1) q ;; (* Partition coupe en deux une liste à partir de pivot *) let partition pivot = let rec parti liste_inf liste_sup nb_inf= function |[] -> (liste_inf,liste_sup,nb_inf) |t::q -> if t<=pivot then parti (t::liste_inf) liste_sup (nb_inf+1) q else parti liste_inf (t::liste_sup) nb_inf q in parti [] [] 0 ;; (* Minimédiane trouve la médiane d'un qroupe de 5 éléments en moins de 8 comparaisons (en fait 7 !!!) *) let minimédiane liste = let med=length liste /2 +1 in let rec fusion_médiane l1 l2 k = match (l1,l2,k) with |[],_,_ -> hd l2 |_,[],_ -> hd l1 |t1::q1,t2::q2,1 -> min t1 t2 |t1::q1,t2::q2,k -> if t1 failwith "Erreur dans minimédiane : liste vide" |[a] -> a |[a;b] -> a |a::b::q -> fusion_médiane (mergesort [a;b]) (mergesort q) med ;; (* minimédiane [1;2;3];; minimédiane [1;2;3;4];; minimédiane [1;2;3;4;5];; *) (* Cette fonction va couper la liste en liste à 5 éléments *) let rec coupe_en_5 = function |[] -> [] |a::b::c::d::e::q -> [a;b;c;d;e]::(coupe_en_5 q) |liste -> [liste] ;; (* coupe_en_5 [1;2;3;4;5;6;7;8;];; *) (* Selectionne va mettre en pratique l'algorithme décrit dans AHU *) let rec selectionne k liste = let n=length liste in if n<75 then k_ième k (mergesort liste) else let temp = map minimédiane (coupe_en_5 liste) in let pivot= selectionne (n/10) temp in let (liste_inf,liste_sup,nb_inf)=partition pivot liste in if k<=nb_inf then selectionne k liste_inf else selectionne (k-nb_inf) liste_sup ;; let n=1000;; let rec cree_liste = function |0 -> [] |n -> (Random.int (n+1))::(cree_liste (n-1)) ;; Random.init (int_of_float (Sys.time()));; let test = cree_liste n;; (* mergesort test;; Sort.list (fun a b -> a<=b) test;; *) selectionne 10 test;;