1. Kota UENISHI
  2. hello

Source

hello / ocaml / qsort.ml


let rec print_array array = match array with
  | []-> print_endline "";
  | a::r -> 
      Printf.printf "%d " a;
      print_array r;;  
  
let rec print_farray array = match array with
  | []-> print_endline "";
  | a::r -> 
      Printf.printf "%f " a;
      print_farray r;;    

(* non-tail-recursive quicksort. general implementation. *)
let rec qsort_nontl comparer list = 
  match list with 
    | [] -> [];
    | hd::tl ->
	let (rhs, lhs) = List.partition (comparer hd) tl in
	  (qsort_nontl  comparer lhs) @ [hd] @ (qsort_nontl comparer rhs);;

(* tail-recursive quicksort without CPS (what is CPS?). of course O(n log n). *)
let qsort comparer list= 
  let rec qs l remain sorted =
    match l, remain with
      | [], [] -> sorted;
      | [], hd::tl ->    qs hd tl sorted;
      | a::[], hd::tl -> qs hd tl (a::sorted);
      | hd::tl, _->
	  let (lhs, rhs) = List.partition (comparer hd) tl in
	    qs lhs ([hd]::rhs::remain) sorted;
  in
    qs list [] [];;

(* random float array generator
   http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4/mltext/ocaml.html#htoc56 *)
let nextrand seed =
  let a = 16807.0 and m = 2147483647.0 in
  let t = a *. seed
  in (t -. m *. floor (t /. m));;
let rec randlist n seed tail =
  if n = 0 then tail
  else randlist (n - 1) (nextrand seed) (seed::tail);;

(* test for short array of int
let integer = 
  let a = [4; 3; 2; 56; 1; 0; -1; 234; 352] in
    print_array a;
    print_array (qsort (<) a);
    print_array (qsort_nontl (<) a);; *)

let list = randlist 1000000 1.0 [];;
(* print_farray b;; *)
Printf.printf "qsort: Length of random float array is %d.\n" (List.length list);;
print_endline "running qsort - tail recursive";;
qsort (<) list;;
print_endline "running qsort - non tail recursive (will stackoverflow): ";;
qsort_nontl (<) list;;