(**** 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;