Module Selsort
A functional implementation of selection sort. Selection sort iteratively
finds a minimal element of a list, removes it and puts it a the
the start of the list.
module SelectionsortFun (E: ORDERED) : (SORT with type elem = E.t) =
struct
type elem = E.t
let rec sort l =
let rec extract_min (l': a list): (a × a list) = (* find and remove a minimum *)
match l' with
[ ] ® raise (Failure ("Empty list"))
| [x] ® (x, [ ])
| x::tl ®
let (min, tl') = (extract_min tl)
in
if E.lt(x, min) then (x, tl) else (min, x::tl')
in
match l with
[ ] ® [ ]
| _ ® let (min, l') = (extract_min l) in min::sort l'
end
Pages last (re-)generated October 28, 2002 (Martin Steffen)