(**** LECTURE 6: Sorting ****)
(* $Id: sorting.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp $ *)
(** Recommended by Stephen K. Park and Keith W. Miller,
Random number generators: good ones are hard to find,
CACM 31 (1988), 1192-1201.
Real number version for systems with 46-bit mantissae
Computes (a*seed) mod m ; should be applied to integers only! **)
local val a = 16807.0 and m = 2147483647.0
in fun nextrandom seed =
let val t = a*seed
in t - m * real(floor(t/m)) end
(*truncate to integer from 1 to k*)
and truncto k r = 1 + floor((r / m) * (real k))
end;
fun randlist (n,seed,seeds) =
if n=0 then (seed,seeds)
else randlist(n-1, nextrandom seed, seed::seeds);
val (seed,rs) = randlist(10000, 1.0, []);
(** insertion sort **)
fun ins (x:real, []) = [x]
| ins (x:real, y::ys) = if x<=y then x::y::ys (*it belongs here*)
else y::ins(x,ys);
fun insort [] = []
| insort (x::xs) = ins(x, insort xs);
(*Quick sort: the appends take only n log n! *)
fun quick [] = []
| quick [x] = [x]
| quick (a::bs) = (*the head "a" is the pivot*)
let fun partition (left,right,[]) : real list =
(quick left) @ (a :: quick right)
| partition (left,right, x::xs) =
if x<=a then partition (x::left, right, xs)
else partition (left, x::right, xs)
in partition([],[],bs) end;
(*Quick sort without append -- slightly quicker*)
fun quik ([], sorted) = sorted
| quik ([x], sorted) = x::sorted
| quik (a::bs, sorted) = (*"a" is the pivot*)
let fun partition (left,right,[]) : real list =
quik (left, a :: quik(right,sorted))
| partition (left,right, x::xs) =
if x<=a then partition (x::left, right, xs)
else partition (left, x::right, xs)
in partition([],[],bs) end;
(*** Merge sorting ***)
fun merge([],ys) = ys : real list
| merge(xs,[]) = xs
| merge(x::xs, y::ys) =
if x<=y then x::merge(xs, y::ys)
else y::merge(x::xs, ys);
(** Top-down merge sort -- like Bird and Wadler, following Sedgewick **)
fun tmergesort [] = []
| tmergesort [x] = [x]
| tmergesort xs =
let val k = length xs div 2
in merge(tmergesort (take(xs,k)),
tmergesort (drop(xs,k)))
end;