Radix Sort Algorithm

Radix sort is a Radix-Based sorting algorithm. This sorting algorithm is useful when number of elements are very large as compared to the number of digits used to represent those elements of the array.

Average Case Complexity : O(b n)
Worst Case Complexity : O(b n)

Basic Idea : 

we sort all the numbers according to the unit place digit, then further we sort the same list according to the tens place digit and we continue doing this and finally after we sort the array as per left-most digit, we will have a sorted array.

Note:- Its important to start the sorting from least significant digit to most significant digit, and NOT the other way to get correct results.

Java Code : 

package Sorting;

import java.util.ArrayList;

public class RadixSort {

      // method to be called to Apply sort, method returns a sorted array

      public static int[] Sort(int[] array){

           

            //find maximum value element in array

            int max = getMaxNum(array);

            //find the number of digits in max number

            int digitCounts = getNumberOfDigits(max);

            //initialize sortIndex

            int SortIndex = 1;

           

            //Continue below procedure till digit count becomes 0

            while(digitCounts !=0){

                 

                  //Initialize radixBucket

                  ArrayList[] RadixBucket = new ArrayList[10];

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

                        ArrayList<Integer> list = new ArrayList<Integer>();

                        RadixBucket[i] = list;

                  }

                  //for every element of input array

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

                        int number = array[i];

                        int index = 0;

                        //calculate index i.e the digit at SortIndex's place

                        for(int j=SortIndex; j!=0; j--){

                              index = number%10;

                              number = number/10;

                        }

                        //fill the element in Bucket at calculated index

                        RadixBucket[index].add(array[i]);

                  }

                  //fill elements back in array in the same order they are filled in Buckets

                  for(int i=0,j=0; j<10; j++){

                        if(RadixBucket[j].size() != 0){

                              for(int k=0; k<RadixBucket[j].size() ; k++){

                                    array[i] = (int) RadixBucket[j].get(k);

                                    i++;

                              }

                        }

                  }

                  //Increase SortIndex and decrease digitCounts

                  SortIndex++;

                  digitCounts--;

            }//repeat the procedure till digitCounts become 0

           

            //now the array is sorted, return the array

            return array;

      }

     

      //method to find the max value element in array

      private static int getMaxNum(int[] array){

            int num = array[0];

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

                  if(array[i] > num){

                        num = array[i];

                  }

            }

            return num;

      }

      //method to find Number of digits in given number

      private static int getNumberOfDigits(int num){

            int numDigits = 0;

            do{

                  num = num/10;

                  numDigits++;

            }while(num != 0);

           

            return numDigits;

      }

}