linearSort.ml

(*
**
** ocaml module LinearSort
**
** Description: Three linear time sorting algorithms!
**
** Author: Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>, (C) 2003
**
** Copyright: See COPYING file that comes with this distribution
** Note: This one is distributed under GPL --> http://www.gnu.org/copyleft/gpl.html
**
*)

open Printf

let print_intarray a = Array.iter (fun x->printf "%d " x) a
let print_floatlist a = List.iter (fun x->printf "%f " x) a

(* for x in a, x is between 0 and k *)
let counting_sort a k =
  let b = Array.make (Array.length a) 0 in
  let c = Array.make (k+1) 0 in (* initially c is an array of 0's *)
    for j = 0 to Array.length a - 1 do
      c.(a.(j)) <- c.(a.(j)) + 1
    done; (* c now contains number of elts equal to i *)
    for i = 1 to k do
      c.(i) <- c.(i) + c.(i-1)
    done; (* c now contains number of elts less than or equal to i *)
    (*printf "c="; print_intarray c; printf "\n";*)
    for j = Array.length a - 1 downto 0 do
      (*printf "j=%d a.(j)=%d c.(a.(j))=%d\n" j a.(j) c.(a.(j));*)
      b.(c.(a.(j))-1) <- a.(j);
      c.(a.(j)) <- c.(a.(j)) -1
    done;
    b

(* specific radix sort code for integers again in a large range 1..256^d *)
let radix_sort a d stable_sort =
  let b = ref a in
    for i = 0 to d-1 do
      b := stable_sort b (* use a stable sort to sort array a on digit i!! *)
    done;
    b

(* input is generated by a randome process that distributes elements
   uniformly over interval [0,1) *)
let bucket_sort a =
  let n = Array.length a in
  let b = Array.make n ([]: float list) in
    for i = 0 to n-1 do
      let ix = int_of_float ( (float_of_int n) *. a.(i) ) in
	b.(ix) <- a.(i)::b.(ix)
    done;
    (*Array.iter (fun x->print_floatlist x; printf"\n") b;*)
    List.concat (List.map (List.sort compare) (Array.to_list b))

let test () =
  printf "linear sort test\n";
  begin
    let a = [| 5; 13; 2; 25; 7; 16; 20; 8; 4 |] in
    let b = counting_sort a 32 in
      print_intarray b; printf "\n"
  end;
  begin
    let a = [| 0.3; 0.1; 0.76; 0.45; 0.95; 0.09; 0.42 |] in
    let b = bucket_sort a in
      print_floatlist b; printf "\n"
  end