(* * * * * * * * * * * * Resource Aware ML * * * * * * * * * * * * * File: * quicksort.raml * * Author: * Jan Hoffmann (2009) * * Resource Bound: * O(n^2) * * Description: * Two implementations of the well known sorting algorithm quicksort. * * The function quicksort does not use a destructive pattern match * and thus consumes quadratic heap-space and quadratic time. * * quicksortD uses the destructive pattern matching to delete * intermediate results. This leads to a linear heap-space and * quadratic time consumption. *) quicksort : L(int) -> L(int) (* works out of the box as implemented in textbooks *) quicksort l = let _=tick(1) in match l with | nil -> nil | (z::zs) -> let (xs,ys) = split (z,zs) in append(quicksort xs, z::(quicksort ys)); split : (int,L(int)) -> (L(int),L(int)) split(pivot,l) = let _=tick(1) in match l with | nil -> (nil,nil) | (x::xs) -> let (ls,rs) = split (pivot,xs) in if x > pivot then (ls,x::rs) else (x::ls,rs); append : (L(int),L(int)) -> L(int) append(l,ys) = let _=tick(1) in match l with | nil -> ys | (x::xs) -> x::append(xs,ys); main = ()