radix sorting algorithm.


Introduction to Radix sort:-

If you had observed in previous sorting algorithms (BubbleSelectioninsertionquick and merge sorting) we have seen how can we sort an array by comparing two adjacent numbers or dividing the array into sub-arrays of 0 or 1 elements. But, Have you ever thought are there any other ways to sort a number without comparing the two numbers directly for their equality? Yes, Radix sort is an example of such sorting. 
 
Radix sort works based on the number of numbers present in a value given. I mean to say a number with 4 digits is always greater than the number with 2 digits( Make sure the most significant digits in the 4 digit number are not zero). By using radix sorting we sort an array of elements based on the number of digits in the value rather than comparing it with other values.
 

The logic of Radix sort:-

Firstly, Let me explain the logic of radix sort in depth by using an example. Let’s say we want to sort the numbers 3221, 1, 10, 9680,123 in the ascending order. Now by looking at this, the biggest number is either 3221 or 9680 as they have 4 digits in them. So now convert all numbers into 4 digit numbers by adding 0’s at the beginning of the number. As a result, the numbers will become 3221,0001,0010,9680,0123.
In the next step, It doesn’t matter how big number we have, we will always have 0 to 9 digits in the given place. So we create 10 sub-arrays. We start comparing the numbers from the least significant digit i.e 0th place. if the value is 0 we push it to the subarray which holds all values with 0. 

Likewise, if the value is 1 in the most significant digit we push it to subarray which holds all values with 1 at its 0th place.  Once all values are pushed to subarrays then we merge them and form a new array. Now that 0th place over we moves to 10th position. Now we compare the numbers for their 10th position value and move them into the subarrays holding respective values. At the end again all values are merged and the same procedure is repeated for 100th and 1000th position to get the sorted array.

See the example below.

Radix sorting

Breaking down radix sort:-

To implement the above logic we need a couple of helper functions to implement the radix sort. They are 

  1. A function which returns the digit counter in a given number.
    Ex: getDigitCount(123432) ,it should return 6.
          getDigitCount(0) ,it should return 1.
          getDigitCount(97) ,it should return 2.
  2. A function which returns the maximum digit count in a given array of numbers by using the above utility. This is the number of times we compare the digit at a particular position and push it to the respective sub-array.
    Ex: getMaxDigitCount({123432,0,97}), it should return 6.
          getMaxDigitCount({1,0,97}), it should return 2.
  3. Finally, Getting a digit at the nth position. To Push a number to a subarray first we need to get the number, That’s why we need this helper function.
    Ex: getDigit(9840,0) should return 0.
           getDigit(9840,1) should return 4, etc.

Pseudocode for radix sort:-

By utilizing the above helper function the pseudocode for the radix sort can be written as shown below.
  1.  Define a function which accepts the array and returns a sorted array.
  2. Get the max number digit count by using the above utility function.
  3.  Loop from 0 to max digit count.
    *. Create 10 sub-arrays(0-9) to hold the matching values.
    *. Place the number into the respective array based on the kth digit.
  4. Replace the values in the array from subarrays holding values based on the kth digit.
  5. Return the sorted array at the end.
Implementation of the radix sort in various languages is as shown below.
public class RadixSort {
    /*
     * This function return the number of digits 
     * existing in the give number
     */
    public static int getDigitCount(int number) {
        int digitCount = 0
        while (number != 0) { 
            number = number / 10
            ++digitCount; 
        } 
        return digitCount;
    }

    /*
     * This function return the maximum number of digit 
     * existing in the largest element in the array
     */
    public static int getMaxDigitCount(int[] array) {
        int maxDigitCount=0;
        for(int i=0;i<array.length;i++) {
            int digitCount = getDigitCount(array[i]);
            if(digitCount>maxDigitCount) {
                maxDigitCount=digitCount;
            }
        }
        return maxDigitCount;
    }
    /*
     * This function return the digit at the given index
     *  from the given number 
     */
    public static int getDigit(int number, int index) {
        return (int) ((number / Math.pow(10, index)) % 10);
    }

public static int[] radixSort(int[] array) {         int mostDigits = getMaxDigitCount(array);

        for (int k = 0; k < mostDigits; k++) {
            Object[] digitBuckets = new Object[10];
            for(int j=0;j<digitBuckets.length;j++) {
                digitBuckets[j]= new ArrayList<Integer>();
            } 
            for (int i = 0; i < array.length; i++) {
                int digit = getDigit(array[i], k);
                ArrayList<Integer> digitArrayList=(ArrayList<Integer>)digitBuckets[digit];
                digitArrayList.add(array[i]);
                digitBuckets[digit]=digitArrayList;
            }
            ArrayList<Integer> mergedArraylist= new ArrayList<Integer>();
            for(int i=0;i<digitBuckets.length;i++) {
                mergedArraylist.addAll((ArrayList<Integer>)digitBuckets[i]);
            }
            for(int i=0;i<array.length;i++) {
                array[i]=mergedArraylist.get(i);
            }
            System.out.println("digit buckets are:-"+mergedArraylist);
            System.out.println("--------------------------------------");
        }
        return array;
    }
    public static void main(String[] args) {
        int[] x= {54,9,1};
        radixSort(x);
    } 
}
function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10
}
function getDigitCount(num) {
    if (num === 0return 1;
    return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function getMaxDigitCount(array) {
    var count = 0;
    for (var i = 0; i < array.length; i++) {
        var currentCount = getDigitCount(array[i]);
        if (currentCount > count) {
            count = currentCount;
        }
    }
    return count;
}
function radixSort(array) {
    var mostDigits = getMaxDigitCount(array);
    for (var k = 0; k < mostDigits; k++) {
        var digitBuckets = Array.from({ length: 10 }, () => []);// this array is to contain the arrays. 
        for (var i = 0; i < array.length; i++) {
            var digit = getDigit(array[i], k);
            digitBuckets[digit].push(array[i]);
        }
        console.log("digit bucket array is:-", digitBuckets);
        array = [].concat(...digitBuckets);
        console.log("array is:-", array);
    }
    return array;
}
console.log(radixSort([113322223302]));

Time complexity of Radix sort:-

Radix sorting is different from all other sorting algorithms when compared with traditional and intermediate sorting algorithms as it sorts the elements based on the values present at nth position. As a result number of comparisions go down drastically. In worst case, if there are n value array to be sorted and largest value has ‘k’ digits in it, Then the process of putting the values into subarrays will be repeated k times for every element in the array i.e n. Hence, The time complexity of the Radix sort is O(nk).
radix sort big(O).