Understanding and Implementing the Radix Sort

RadixSort.md

Radix Sort

This is a sorting algorithm that sorts the array in stable, non-comparision way. We never compare anything in this.

This is based on the the Count Sort. Learn about this it's very very simple. Count sort usually works best when we have small range of number that we want to sort. Why only small range?? Because in the algorithm we find the maximum number from array and create the array of size MaxNumber + 1 which is used to keep the count/freq of each element that is present in the array. Go and learn yourself.

Back to Radix Sort

• first, find the maximum number from the array in this algorithm also.
• second, We find the number of digits in this max number.
• third, we count sort the array on the basis of digits one by one. starting from the least significant bit (LSB). Those who doesn't have that bit 0 is considered at that place.

Once you are done with all the iterations you will see your array is sorted.

Basic Math:

1. To find the digits in an number you can use the log, For example for decimal numbers it will be $\log_{10}(num) + 1$
2. To find the nth digit from the LSB side(n = 1 means ones(exp = 1), n = 2 means tens(exp = 10), n = 3 means hundreds(exp = 100) of a number we can use (number / exp) % 10

Algorithm

1. Find the maximum number from array maxElement
2. Instead of number of digits calculation I will loop untill the number / exp > 0 by increasing exp by 10 times.
3. Now do the count sort for each iteration and this will sort the array on the basis of exp digits Use the count sort
4. We need the count array size of 10
5. Then we update the count array to effectively find the position of number in final array for that bit.
6. We start from the back so that the sort remain stable.

Example:

nums = 456, 4, 54, 10, 13, 98, 87, 6

Max element = 456 Having 3 digits so we will pass for 3 times

Pass 1:

• Original nums = 456, 4, 54, 10, 13, 98, 87, 6
• Count array = 1, 0, 0, 1, 2, 0, 2, 1, 1, 0
• Updated count array = 1, 1, 1, 2, 4, 4, 6, 7, 8, 8 ( this will never exceed the size of the original array as at end is sum of all freq)
• updated nums after 1 pass = 10, 13, 4, 54, 456, 6, 87, 98

Pass 2:

• Original nums = 10, 13, 4, 54, 456, 6, 87, 98
• Count array = 2, 2, 0, 0, 0, 2, 0, 0, 1, 1
• Updated count array = 2, 4, 4, 4, 4, 6, 6, 6, 7, 8
• updated nums after 1 pass = 4, 6, 10, 13, 54, 456, 87, 98

Pass 3:

• Original nums = 4, 6, 10, 13, 54, 456, 87, 98
• Count array = 7, 0, 0, 0, 1, 0, 0, 0, 0, 0
• Updated count array = 7, 7, 7, 7, 8, 8, 8, 8, 8, 8
• updated nums after 1 pass = 4, 6, 10, 13, 54, 87, 98, 456

Walah, the array is sorted.

code:

class Solution {
  public:
  
    vector<int> countSort(vector<int>&arr, int exp) {
        int n = arr.size();
        vector<int> count(10);
        
        // fill the count array with count of digit at exp place
        for (int num: arr) {
            int digitExpPlace = (num / exp) % 10;
            count[digitExpPlace]++;
        }
        
        // now agreegate count array to get the index to fill
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // now fill the integers in array at their correct place 
        // by exxp place value
        // we start from back so that the arr remain stable and the 
        vector<int> newArr(n, 0);
        for (int i = n - 1; i >= 0; i--) {
            newArr[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        return newArr;
    }
    void radixSort(vector<int>& arr) {
        int maxElement = *(max_element(arr.begin(), arr.end()));
        //pass through the number of digits times in maxElement
        //or go till the maxElement/exponent is greater than 0
        
        for (int exp = 1; maxElement/exp > 0; exp *= 10) {
            arr = countSort(arr, exp);
        }
        
        return;
    }
};