Previous Contents Next

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 (EORDERED) : (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 (mintl') = (extract_min tl)
         in 
         if E.lt(xminthen (xtlelse (minx::tl')
       in
       match l with
         [ ] ® [ ]
       | _ ® let (minl') = (extract_min lin min::sort l'
   end


January 31, 2002
Previous Contents Next