# hello / ocaml / qsort.ml

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58``` ``` 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;; ```