Radix Sort - Java Code

A non-comparative sorting algorithm

• Key Idea: Sort the Least Significant Digit first
• Worst case time complexity: O( wn ), where w = no. of digits, n = no. of keys

Algorithm

Algorithm RadixSort(A)

       Input: An integer array A

       Output: A sorted array A

d ← no. of digits of maximum number of A

for i = 1 to d do

Any stable sort on A based on the digit i (Usually counting sort)

Java Code

public void radixSort(int[] arr) {

       // Getting maximum item for the number of digits required to sort

       int maxItem = getMaximumItem(arr);

       int noOfDigits = String.valueOf(maxItem).length();

       for (int digit = 1; digit <= noOfDigits; digit++) {

              countSort(arr, digit);

       }

}

public void countSort(int arr[], int digit) {

       int divisor = (int) Math.pow(10, digit - 1);

       int[] count = new int[10];

       // Storing the occurrences/frequencies of the items

       for (int i = 0; i < arr.length; i++) {

              int itemDigit = (arr[i] / divisor) % 10;

              count[itemDigit]++;

       }

       // Storing the cumulative frequencies

       for (int i = 1; i < 10; i++) {

              count[i] += count[i - 1];

       }

       // Build the sorted array based on the current digit

       int[] sortedArray = new int[arr.length];

       for (int i = arr.length - 1; i >= 0; i--) {

              int itemDigit = (arr[i] / divisor) % 10;

              sortedArray[count[itemDigit] - 1] = arr[i];

              count[itemDigit]--;

       }

       // Copying the sorted array to the original array

       for (int i = 0; i < arr.length; i++) {

              arr[i] = sortedArray[i];

       }

}

public int getMaximumItem(int arr[]) {

       int maxItem = arr[0];

       for (int i = 1; i < arr.length; i++) {

              if (arr[i] > maxItem) {

                     maxItem = arr[i];

              }

       }

       return maxItem;

}