Radix Sort in Go (Golang)

Share on Facebook0Tweet about this on Twitter4Share on Google+1Share on Reddit0Share on StumbleUpon6

Radix Sort is a relatively old (discovered in 1887 by Herman Hollerith), non-comparitive integer sorting algorithm, which sorts data by comparing various integers individual digit position and value. In many ways Radix Sort in Go reflects and builds off Counting Sort, and I recommend reviewing that algorithm as well.

Radix Sort

Essentially, the algorithm is is follows:

  • Receive an unsorted array of integers, often referred/represent a key
  • Iterate from most to least or least to most significant digits
  • Each iteration sort all of the values of the current significant digit the array

* A key in this case, is an integer value, which is associated with other data, such as birth date, location, etc.

To better demonstrate, we will complete an example problem with four integers to sort:

Original: 100, 12, 1, 5

{ 100, 12, 1, 5 } -> { 100, 1, 12, 5 }
{ 100, 1, 12, 5 } -> { 1, 5, 100, 12 }
{ 1, 5, 100, 12 } -> { 1, 5, 12, 100 }

Sorted: 1, 5, 12, 100

That’s it! If you carefully watch the “100” value through various iterations, you’ll notice each time we simply move one significant digit to the left and resort using that digit. It is also possible to go left to right, i.e. most significant digit to least significant digit, but I chose this implementation.

Example by Hand

Implementing this algorithm requires a bit more finesse than I let on. First, let me state that there are several ways to implement Radix Sort, and this is not the sole correct method. In order to efficiently implement Radix Sort, we use something called “buckets” which will store the index of the sorted significant digits, similar to Counting Sort. 

For example, the bucket for iteration one would be as follows:

 array[100, 1, 12, 5] -> bucket[0, 1, 2, 2, 2, 4, 4, 4, 4, 4]

The reason for the repeated numbers is because we have a value of 0, 1, 2, and 5 for the value at the given significant digit (in this case the 1’s place). The implementation I am using adds a number to the bucket[index] when ever there is a new value for a given significant digit. For instance, the reason we repeat 2 twice after the initial 2 is because there is no “3 or 4” in the any of the integers current significant digits, in the array we are sorting (wow that was a mouthful). 

If we then added the number 101 to the list, we would have the following bucket:

 array[100, 101, 1, 12, 5] -> bucket[0, 1, 3, 3, 3, 4, 4, 4, 4, 4]

Notice, the orange 2 has changed to a orange 3, this is because the new 2-value bucket starts at 3rd position in the semi-sorted array. 

Now let’s add the number 8 to the list, we will have the following bucket:

array[100, 101, 1, 12, 58] -> bucket[0, 1, 3, 3, 3, 4, 4, 4, 5, 5]

Reflect that 8 is the 5th index in the sorted significant digit array, represented with the number 5 in the 8th index/position in the bucket array.

  • Time: O(nk), where n is the number of elements and k is the number of bits per element
  • Space: O(n + k), where n is the number of elements and k is the number of bits per element

Code | Radix Sort in Golang

(viewable/forkable on Github)

Shameless  Plug: It took about 20 minutes to code this up. If you need help with Go programming feel free to book me for tutoring/program writing.

Output:

Running Radix Sort Go Example!
———————————-

Unsorted List: [10 2 303 4021 293 1 0 429 480 92 2999 14]

Running Radix Sort in Golang on Unsorted List

Sorting: 1’s place [10 2 303 4021 293 1 0 429 480 92 2999 14]

Bucket: [0 3 5 7 9 10 10 10 10 10]
Sorting: 10’s place [10 0 480 4021 1 2 92 303 293 14 429 2999]

Bucket: [0 4 6 8 8 8 8 8 8 9]
Sorting: 100’s place [0 1 2 303 10 14 4021 429 480 92 293 2999]

Bucket: [0 7 7 8 9 11 11 11 11 11]
Sorting: 1000’s place [0 1 2 10 14 4021 92 293 303 429 480 2999]

Bucket: [0 10 10 11 11 12 12 12 12 12]

Sorted List: [0 1 2 10 14 92 293 303 429 480 2999 4021]

Feel free to review my article on Radix Sort in C as well, the results are exactly the same as Radix Sort in Go.

Summary

Unfortunately, due to its simplicity and the requirement of fixed-length integer keys, this algorithm is often overlooked or unused. There are several applications of Radix Sort which can be useful, such as parallel computing, but Radix Sort is not really a “general purpose” sorting algorithm. For the average or more general use case quicksort or merge sort is probably a safer bet. If you are still interested I recommend reading further discussion on stack exchange and stack overflow.

Related Articles

Share on Facebook0Tweet about this on Twitter4Share on Google+1Share on Reddit0Share on StumbleUpon6

 Subscribe

If you enjoyed this article subscribe via email, it's free!

Plus exclusive email only content and problem solutions.

View Archived Emails (no surprises, no spam!)

One comment on “Radix Sort in Go (Golang)

  1. Something I love about Go is the elegance of the interfaces- like how the sort.Interface works for all comparison sorts, regardless of the underlying data structure.
    On a similar note, radix sort can be used on any type that has the idea of ordered places within the key. That means digits in a number, letters in a string, or even date/time values: year/month/day/hour/min/sec, distances as miles/feet/inches etc. I would have used metric as an example, except that’s the same as using decimal digits.
    Anyway, if there was an interface that represented comparable orders of magnitude for each key in a collection similar to how sort.Interface is represented, you would have a useful general-purpose O(n+k) sorting algorithm.

Leave a Reply

Your email address will not be published.


1 × = two

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">