How does Radix Sort work?

Question

I don't know why this is so hard for me to wrap my head around. I've looked through the wiki pages, and pseudo code (as well as actual code) trying to understand how radix sort algorithms work (with respect to buckets).

Am I looking into the wrong thing here? Should I be looking into bucket sort maybe? Can someone give me a dumbed down version of how it works? For reference, here is a codeblock that supposedly performs a radix sort:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

And I've looked at non-recursive solutions also:

void radixsort(int *a, int arraySize)
{
    int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
    for(i = 0; i < arraySize; i++) {
        if(a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1; 
    while(maxVal/digitPosition > 0) {
        // reset counter 
        int digitCount[10] = {0};

        // count pos-th digits (keys) 
        for(i = 0; i < arraySize; i++)
            digitCount[a[i]/digitPosition%10]++;

        // accumulated count 
        for(i = 1; i < 10; i++)
            digitCount[i] += digitCount[i-1];

        // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

        for(i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        cout << "pass #" << pass++ << ": ";
        digitPosition *= 10;
    } 

}

Specifically, this line is giving me troubles. I've tried walking through it with pen and paper, but I still can't figure out what this is doing:

   // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

Answer 1

In mathematics, radix means base, where decimal would be base 10. Imagine you have numbers some of which having more than one digits like

5, 213, 55, 21, 2334, 31, 20, 430

For simplicity, say you want to use the decimal radix (=10) for sorting. Then you would start by separating the numbers by units and then putting them together again; next you would separate the numbers by tens and then put them together again; then by hundreds and so on until all the numbers are sorted. Each time you loop, just read the list from left to right. You can also imagine you are separating the numbers into buckets. Here is an illustration using 5, 213, 55, 21, 2334, 31, 20, 430

Separate by units:

• zeros: 20, 430

• ones: 21, 31

• twos:

• threes: 213

• fours: 2334

• fives: 5, 55

  Back together: 20, 430, 21, 31, 213, 2334, 5, 55

To put them back together, first read the zeroes bucket, then the ones bucket, then so on, until you read the nines bucket.

Separate by tens:

• zeros: 05

• ones: 213

• twos: 20, 21

• threes: 430, 31, 2334,

• fours:

• fives: 55

  Back together: 5, 213, 20, 21, 430, 31, 2334, 55

Separate by hundreds:

• zeros: 005, 020, 021, 031, 055

• ones:

• twos: 213

• threes: 2334

• fours: 430

• fives:

  Back together: 5, 20, 21, 31, 55, 213, 2334, 430

Separate by thousands:

• zeros: 0005, 0020, 0021, 0031, 0055, 0213, 0430

• ones:

• twos: 2334

• threes:

• fours:

• fives:

  Back together: 5, 20, 21, 31, 55, 213, 430, 2334

You are now done. I saw a nice code for this on Geekviewpoint both in Java and in python

Answer 2

This is the basic flow of quicksort.

For 1st pass: we sort the array on basis of least significant digit (1s place) using counting sort. Notice that 435 is below 835, because 435 occurred below 835 in the original list.

For 2nd pass: we sort the array on basis of next digit (10s place) using counting sort. Notice that here 608 is below 704, because 608 occurred below 704 in the previous list, and similarly for (835, 435) and (751, 453).

For 3rd pass: we sort the array on basis of most significant digit (100s place) using counting sort. Notice that here 435 is below 453, because 435 occurred below 453 in the previous list, and similarly for (608, 690) and (704, 751).

For more details you can refer to this blog on codingeek and have clear understanding.

Answer 3

Think of a deck of cards. You first sort it by suit in four piles. Then you put those four piles on top of one another and now sort into 13 piles based on rank. Put those together and you now have a sorted deck.

Answer 4

may be my code could help you:)

Here is python`s code of Radix Sort:

import random,time

from random import randint

A=[random.randint(1,1212) for i in range(23)]


length = len(str(max(A)))

print(length) 

rang = 10

print(A)

start=time.time()

for i in range(length):

B = [[] for k in range(rang)]

for x in A:

    figure =x // (10**i) % 10

    B[figure].append(x)

A = []

for k in range(rang):

    A+=B[k]

end=time.time()

print(end-start)

print(A)