Understanding Radix Sort, With Examples

Have you ever had a large group of data and wanted to organize it without having to look at every single piece? Radix sort is one of the easiest ways to examine your data, allowing you to handle other business. 

In this article, we break down the functions of this simple algorithm. From database organization to computer graphics, there are so many ways to implement radix sort into your program. We even provide the syntax to get you started. Let’s begin so you can get your data organized.

What Is Radix Sort?

When you need to sort large groups of data, one of the basic functions in programming is Radix sort. This algorithm works by sorting numbers one digit at a time.

Here’s how it works:

First, the function examines the least significant digit (the 1 spot) of each piece of data and sorts them all from least to greatest. Then, it moves on to the next least significant digit (the 10 spots) and organizes them again. It continues with this pattern until all the numbers are organized. Let’s show how this works in an example.

Suppose we want to radix sort this group of numbers: 49, 5, 473, 60, 380, 21, 55.

The algorithm would first examine the ones place of each number and sort them from least to greatest. Here’s how the function would organize this group: 60, 380, 21, 473, 5, 55, 49.

Next, the algorithm would move on to the tens place of each number and reorganize. Here’s what that would look like: 5, 21, 49, 55, 60, 473, 380.

The algorithm would continue on with this pattern until all the numbers are sorted. In this case, the radix sort would end like this: 5, 21, 49, 55, 60, 380, 473.

What Is the Syntax for Radix Sort in Programming?

Because this function is a foundational action, it’s easily applied in most programming languages, so long as they provide support for arrays and basic mathematical operations. Here’s a rudimentary syntax for radix sort in Python:

def radixSort(array):
    maxElement = max(array)
    digitPosition = 1

    while maxElement // digitPosition > 0:
        countingSort(array, digitPosition)
        digitPosition *= 10

def countingSort(array, digitPosition):
    count = [0] * 10
    output = [0] * len(array)

    for element in array:
        index = (element // digitPosition) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i-1]

    for i in range(len(array)-1, -1, -1):
        index = (array[i] // digitPosition) % 10
        output[count[index]-1] = array[i]
        count[index] -= 1

    for i in range(len(array)):
        array[i] = output[i]

What Are the Applications of This Algorithm?

Because of how efficiently the function can organize large groups of data, it has common uses in sorting major databases. You’ll find this algorithm used for financial transactions and even medical records for healthcare organizations. 

Here’s what a radix sort code would look like for sorting large databases:

def radix_sort_database(db):
    max_value = max(db)
    digits = len(str(max_value))
    for i in range(digits):
        buckets = [[] for _ in range(10)]
        for value in db:
            digit = (value // 10 ** i) % 10
            buckets[digit].append(value)
        db = [value for bucket in buckets for value in bucket]
    return db

Additionally, this algorithm can help sort strings by their ASCII values. This helps search engines organize web page titles.

This is how you might code radix sort to string sort data:

def radix_sort(strings):
    max_length = len(max(strings, key=len))
    for i in range(max_length - 1, -1, -1):
        buckets = [[] for _ in range(256)]
        for string in strings:
            if len(string) > i:
                buckets[ord(string[i])].append(string)
            else:
                buckets[0].append(string)
        strings = [string for bucket in buckets for string in bucket]
    return strings

Finally, graphic designers might use this algorithm to sort pixels by color values. It can substantially cut the time it takes to edit large images or even video files. 

Here’s how you might code radix sort organize pixels:

def radix_sort_pixels(pixels):
    max_value = 255
    for shift in (16, 8, 0):
        buckets = [[] for _ in range(256)]
        for pixel in pixels:
            bucket_index = (pixel >> shift) & max_value
            buckets[bucket_index].append(pixel)
        pixels = [pixel for bucket in buckets for pixel in bucket]
    return pixels