Code source du tri "casiers"

let min_max_liste liste=
   let rec min_max l mini maxi=
       match l with
       |[]->mini,maxi
       |a::tt->min_max tt (min mini a) (max maxi a); in
   match liste with
   |[]->failwith "liste vide"
   |tt::qq->min_max qq tt tt;;
(* val min_max_liste : 'a list -> 'a * 'a = <fun> *)

let rec rempli_casier liste tableau indice=
   match liste with
   |[]->();
   |a::q->   tableau.(a-indice)<-tableau.(a-indice)+1;
       rempli_casier q tableau indice;;
(* val rempli_casier : int list -> int array -> int -> unit = <fun> *)

let recompose_liste tableau indice=
   let result=ref([]) in
   for i=Array.length(tableau)-1 downto 0 do
       for j=tableau.(i)-1 downto 0 do
           result:=(i+indice)::(!result);
       done;
   done;
   (!result);;
(* val recompose_liste : int array -> int -> int list = <fun> *)

let tri_casier liste=
   let (mini,maxi)=min_max_liste liste in
   let tableau=(Array.make (maxi-mini+1) 0) in
   rempli_casier liste tableau mini;
   recompose_liste tableau mini;;
(* val tri_casier : int list -> int list = <fun> *)