Module Quicksort

Module Quicksort

A functional implementation of quicksort. The divide-and-conquer approach is visible in the recursive inner sort-function: It chooses as pivot the first element. Using the auxiliary function filter,¹ it splits the remainder of the list into two halves, the elements less or equal the pivot and those larger than the pivot. The sublists are sorted and, together with the pivot in the middle, put together to the sorted list.

module QuicksortFun (E: ORDERED) : (SORT with type elem = E.t) =
     struct
       type elem = E.t

       let rec filter p l = match l with (* auxiliary function *)
         [ ] ® [ ]
       | x :: tl ®
           if (p x)
           then x::(filter p tl)
           else filter p tl

       let rec sort (l : elem list) =
         match l with
           [ ] ® [ ]
         | x :: tl ® (* x = pivot *)
             sort (filter (function y ® E.lt(y,x)) tl)
             @ [x] @
             sort (filter (function y ® E.geq(y,x)) tl)
     end
January 31, 2002