Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does Radix Sort work?

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]; 
like image 507
MrDuk Avatar asked Feb 05 '13 21:02

MrDuk


People also ask

How radix sort works explain?

Radix sort works by sorting each digit from least significant digit to most significant digit. So in base 10 (the decimal system), radix sort would sort by the digits in the 1's place, then the 10's place, and so on. To do this, radix sort uses counting sort as a subroutine to sort the digits in each place value.

Why radix sort is used?

Radix sort can be applied to data that can be sorted lexicographically, such as words and integers. It is also used for stably sorting strings. It is a good option when the algorithm runs on parallel machines, making the sorting faster.

How is radix sort calculated?

The time complexity of radix sort is given by the formula,T(n) = O(d*(n+b)), where d is the number of digits in the given list, n is the number of elements in the list, and b is the base or bucket size used, which is normally base 10 for decimal representation.

Which sorting algorithm is used in radix sort?

Radix sort uses a stable sorting algorithm as a subroutine to sort the digits. We've used a variation of counting sort as a subroutine here that uses the radix to sort the digits in every position. Counting sort is a stable sorting algorithm and it works well in practice.


1 Answers

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

like image 70
Konsol Labapen Avatar answered Sep 19 '22 00:09

Konsol Labapen