Module Bubblesort

Module Bubblesort

A functional implementation of bubble-sort.
module BubblesortFun (E: ORDERED) : SORT with type elem = E. t =
   struct
     type elem = E.t

     let rec bubbleone (l1,l2) =
       match l1 with
         [ ] ® ([ ], l2)
       | [x] ® ([ ],x::l2)
       | x1::x2::l ®
           if (x1 £ x2)
           then
             let (l1', l2') = bubbleone(x2::l, l2)
             in
             (x1::l1', l2')
           else
             let (l1', l2') = bubbleone(x1::l, l2)
             in
             (x2::l1', l2')

     let sort l =
       let rec bubble_h(l1, l2) =
         match l1 with
           [ ] ® l2
         | _ ® bubble_h (bubbleone(l1,l2))
       in
       bubble_h (l, [ ])
   end
January 31, 2002