Radix Sort in C

Share on Facebook1Tweet about this on Twitter5Share on Google+2Share on Reddit4Share on StumbleUpon17

Radix Sort is a relatively old being discovered in 1887 by Herman Hollerith, and it is a non-comparitive integer sorting algorithm. In many ways Radix Sort in C is an extension of Counting Sort in C, which I recommend reviewing as well, as it will provide must of the background for Radix Sort.

Radix Sort

The algorithm follows the following pattern:

  • 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 can be associated with other data, such as birth date, location, etc.

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

Original: 100, 12, 1, 5

{ 100, 1215 } -> { 1001, 125 }

Radix Sort in C - Bin1 - Example
{ 100, 1, 12, 5 } -> { 1, 5, 100, 12 }

bin2

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

Radix Sort in C - Example - bin3

Sorted: 1, 5, 12, 100

Notice, if you watch the “100” through various iterations, you’ll see it is simply move one significant digit to the left and we sort by that digit or 10’s place. It is also possible to go left to right, i.e. most significant digit to least significant digit, but this is the more common method.

Example by Hand

Implementing this algorithm requires a bit more handy work than I let on. First, let me make it clear that there are several ways to implement Radix Sort in C (or out of C), and this is not a clearly defined “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:

Note: bucket[index to array position]

array[1001, 125] -> bucket[012, 22, 3, 3, 3, 3, 3]

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. 

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

 array[100, 1011, 125] -> bucket[ 013, 3, 34, 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, 1011, 1258] -> bucket[013, 3, 34, 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 C Algorithm

Feel free to fork the following code on Github

Output:

Running Radix Sort Example in C!
———————————-

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

Running Radix Sort 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]

You can also review my Go implementation: Radix Sort in Go, the numbers are the same!

Summary

Due to its reliance on memory and the requirement of fixed-length integer keys, this algorithm is often overlooked or unused (reasonably so). There are several applications of Radix Sort which can be useful, such as parallel computing, but Radix Sort is not really a “general purpose” or “everyday use” 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
Recommended Books

Share on Facebook1Tweet about this on Twitter5Share on Google+2Share on Reddit4Share on StumbleUpon17

 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!)

Leave a Reply

Your email address will not be published.


6 + six =

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="">