Radix sort - Forest23557/aLevel

Untitled-1

About Radix Sort

Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order.

Suppose, we have an array of 9 elements. First, we will find the largest element in the array. Second step, we will sort elements based on the value of the unit place. Then, we will sort elements based on the value of the tenth place. This process goes on until the last significant place.

Working of Radix Sort

Let's see how it works with an example. Let's consider the following array:

Iteration 1

Let's start with the digits in ones place:

After the first iteration, the array now looks like:

Iteration 2

Let's move on to the digits in tens place:

Now the array looks like:

We can see that the number 7 has occupied the first position in the array because it doesn't have any digit in the tens place. We can also have it if a number has a 0 in the tens place.

Iteration 3

Let's move on to the digits in hundreds place:

And now we have:

And algorithm stops here because the array is sorted.

Radix Sort Complexity

Time Complexity
Best	O(n+b)
Worst	O(n+b)
Average	O(n+b)
~
Space Complexity	O(n+b)

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for the decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be O(log_b_(k)). So overall time complexity is O((n+b) * log_b_(k)). Which looks more than the time complexity of comparison-based sorting algorithms for a large k. Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes O(nLogb(n)). But it still doesn’t beat comparison-based sorting algorithms. What if we make the value of b larger? What should be the value of b to make the time complexity linear? If we set b as n, we get the time complexity as O(n). In other words, we can sort an array of integers with a range from 1 to nc if the numbers are represented in base n (or every digit takes log_2_(n) bits).

If we take very large digit numbers or the number of other bases like 32-bit and 64-bit numbers then it can perform in linear time however the intermediate sort takes large space. This makes radix sort space inefficient. This is the reason why this sort is not used in software libraries.

Radix Sort code in Java

// A utility function to get maximum value in array
static int getMax(int[] array) {
    int max = array[0];
    int length = array.length;
    for (int i = 1; i < length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

// A function to do counting sort of array according to
// the digit represented by placeValue.
static void countSort(int[] array, int placeValue) {
    int range = 10; // decimal system, numbers from 0-9
    int length = array.length;
    int[] output = new int[length]; // output array
    int i;
    int[] frequency = new int[10];

    Arrays.fill(frequency, 0);

    // calculate the frequency of digits
    for (i = 0; i < length; i++) {
        int digit = (array[i] / placeValue) % range;
        frequency[digit]++;
    }

    // Change frequency[i] so that frequency[i] now contains
    // actual position of this digit in output
    for (i = 1; i < 10; i++) {
        frequency[i] += frequency[i - 1];
    }

    // Build the output array
    for (i = length - 1; i >= 0; i--) {
        int digit = (array[i] / placeValue) % range;
        output[frequency[digit] - 1] = array[i];
        frequency[digit]--;
    }

    // Copy the output array to array, so that array now
    // contains sorted numbers according to current
    // digit
    for (i = 0; i < length; i++) {
        array[i] = output[i];
    }
}

// The main function to that sorts array
// using Radix Sort
static void radixSort(int[] array) {
    int length = array.length;

    // Find the maximum number to know number of digits
    int max = getMax(array);

    // Do counting sort for every digit. Note that
    // instead of passing digit number, placeValue is passed.
    // placeValue is 10^i where i is current digit number
    for (int placeValue = 1; max / placeValue > 0; placeValue *= 10) {
        countSort(array, placeValue);
    }
}

// A utility function to print an array
static void print(int[] array) {
    System.out.println(Arrays.toString(array));
}

// Main driver method
public static void main(String[] args) {
    int[] array = {387, 468, 134, 123, 68, 221, 769, 37, 7};
    
    // Showing the array before sorting       
    print(array);

    // Function Call
    radixSort(array);
    print(array);
}

To the beginning

Radix sort - Forest23557/aLevel_Java GitHub Wiki

Table of contents

About Radix Sort