Home > FUN > Radix Sort in F#

Radix Sort in F#

I have spent many years programming in Haskell, but have also recently started dabbling in F# and Ocaml. I would count myself as a big proponent of the Functional Programming paradigm.

Just as a practice I thought I would implement a Radix sort algorithm in F# for unsigned 32bit integers. Radix sort algorithms use a Radix in order to sort the elements in a list or array. This means that you must be able to define a Radix for the data type which you are trying to sort, but has the advantage that the time complexity of the algorithm is only linear in the number of elements to be sorted (multiplied by a constant that relates to the size of the radix), compared to O(n log n) for most partition sort algorithms.

For this implementation, I shall use the bits as the Radix. This means that each step of the sort algorithm splits the list into two, depending on the value of a single bit in each element, keeping all the elements in these sublists in the same order they appeared in the original list. The algorithm works by splitting the list depending on the least significant bit of each element, and then joining the resultant sublists, before repeating the process depending on the next least significant bit… this repeats until the last step where the splitting depends on the most significant bit of the elements, and the final joined list is ordered. I am sure there are much better definitions of a radix sort on the web, but I thought this would be an interesting initial experiment with F#.

Some of these functions my well be in the library, but my current knowledge of the library is lacking slightly, so I have implemented everything I don’t know about.

The first definition is a function that simply returns a Boolean value of whether the input integer is equal to zero. This achieved using pattern matching.

let is0 x =
  match x with
    0 -> true
  | n -> false

The next function defines how the list is split depending on the Radix. The first argument is the position of the bit which is the current Radix, and the second argument is the input list. The recursive sub-function actually does the work using a pair of accumulators.

// splits a list of integers in half depending on the value of the nth bit of the integers
let splitBy n xxs =
   let rec splitBy' n' xxs' (oz,iz) =
      match xxs' with
        [] -> (oz,iz)
      |  x :: xs -> splitBy' n' xs (if is0 ((x >>> n') &&& 1) then (x::oz,iz) else (oz,x::iz))
   splitBy' n xxs ([],[])

You’ve probably noticed that the lists returned by the previous function actually contain the elements in the reverse order in which they appear in the input list. So, we will need a function that reverses a list. This can also be achieved using an accumulator.

//simple reverse list implemented using an accumulator e.g. extra list to move elements into
let reverse ls =
   let rec reverse' (xs,scratch) =
      match xs with
        [] -> scratch
      | x :: xs -> reverse' (xs,x :: scratch)
   reverse' (ls,[])

We can use the reverse function when we want to join the two lists that are created at each step of the algorithm. I have used the list concatenation function from the library.

let join (oz,iz) = List.concat [reverse oz;reverse iz]

Each step of the algorithm can now be defined. The first argument still defines which bit you’re working with, and the second argument is the input list.

let sortBy n xs = join (splitBy n xs)

The algorithm is completed by running the algorithm recursively over all 32 bits in the unsigned 32 bit integers.

// recursive algorithm to sort depending on LSB upto MSB e.g. bits 0 to 31
let sort xs =
   let rec sort' n xs' =
      match n with
        0 -> xs'
      | i -> sortBy (i-1) (sort' (i-1) xs')
   sort' 32 xs

and that is it… An implementation of Radix sort in F#.
Comments Please.

Advertisements
Categories: FUN
  1. May 8, 2014 at 04:00

    Everything is very open with a precise explanation of the issues.
    It was really informative. Your website is very useful. Thank you for
    sharing!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: