Program to Radix sort in java


Contents of page >
  • Steps to sort array using radix sort in java >
  • Example to sort array using radix sort by using the above steps in java >
  • Full Program/SourceCode/Example to sort array using radix sort in java>
  • Complexity of radix sort in java >


Steps to sort array using radix sort in java >
First all the array elements are divided into group of 10 (i.e. in buckets), according to the value of their 1’s
Digit. (Please note number of groups may be less  than 10 - see below example)

Then all of these 10 groups are reassembled. At this stage elements whose 1’s digit is ending with 0 go first, then elements whose 1’s digit is ending with 1 and so on till elements whose 1’s digit is ending with 9.

Then array elements are divided into group of 10, according to the value of their 10’s
Digit.

Then all of these 10 groups are reassembled. At this stage elements whose 10’s digit is ending with 0 go first, then elements whose 10’s digit is ending with 1 and so on till elements whose 10’s digit is ending with 9.


Example to sort array using radix sort by using the above steps in java >
821 201 112 634 891 109 100 405 503 892 > Array is unsorted
(100) (821, 201, 891) (112, 892) (503) (634) (405) (109) > Array is sorted on 1s digit
(100, 201, 503, 405, 109) (112) (821) (634) (891, 892) > Array is sorted on 10s digit
(100, 109, 112) (201) (405) (503) (634) (821, 891, 892) > Array is sorted on 100s digit
100 109 112 201 405 503 634 821 891 892) > Array is sorted





Full Program/SourceCode/Example to sort array using radix sort in java>
/**
*  write a program to sort array using Radix Sort in java.
*/
public class RadixSortAlgorithmExample {
   /**
   * Declare initialize array which has to be sorted using Radix sort in java
   */
   private int[] arr = { 12, 3, 8, 9, 1, 14, 6, 7, 5, 89 };
   /**
   * This method Sort Array using Radix Sort in java
   */
   public void radixSort() {
          int i,
                 j = 1,
                 temp = arr[0];
          int num = arr.length;
          int[] arr2 = new int[20];
         
          for (i = 1; i < num; i++){
                 if (arr[i] > temp){
                       temp = arr[i];
                 }
          }
         
          while (temp / j > 0) {
                 int[] bucketArray = new int[10];
                 for (i = 0; i < num; i++){
                       bucketArray[(arr[i] / j) % 10]++;
                 }
                
                 for (i = 1; i < 10; i++){
                       bucketArray[i] += bucketArray[i - 1];
                 }
                
                 for (i = num - 1; i >= 0; i--){
                       arr2[--bucketArray[(arr[i] / j) % 10]] = arr[i];
                 }
                
                 for (i = 0; i < num; i++){
                       arr[i] = arr2[i];
                 }
                
                 j *= 10; //Always multiply by 10 to move from 0's to 10's to 100's ....
                
          } //End while loop
   } //End Radix sort method
  
   /**
   * This method Display Array in java
   */
   public void display() {
          for (int i = 0; i < arr.length; i++) {
                 System.out.print(arr[i] + " ");
          }
   }
   public static void main(String[] args) {
          RadixSortAlgorithmExample radixSort = new RadixSortAlgorithmExample();
          System.out.print("Display Array elements before Radix sorting : ");
          radixSort.display(); // display unsorted array
          radixSort.radixSort(); // radix sort the array
          System.out.print("\nDisplay Array elements after Radix sorting  : ");
          radixSort.display(); // display sorted array
   }
}
/*output
Display Array elements before Radix sorting : 12 3 8 9 1 14 6 7 5
Display Array elements after Radix sorting  : 1 3 5 6 7 8 9 12 14
*/


Complexity of radix sort in java >

Radix Sort complexity worst case =  O(nk)
Radix Sort average case = O(nk)
Radix Sort best case = O(nk)

Summary >
So in this data structure tutorial we learned

Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.



eEdit
Must read for you :