Day_35_RadixSort.java

package com.TrX;

class Day_35_RadixSort {
    int getMax(int a[], int n) {
        int max = a[0];
        for(int i = 1; i<n; i++) {
            if(a[i] > max)
                max = a[i];
        }
        return max; //maximum element from the array
    }
    void countingSort(int a[], int n, int place) // function to implement counting sort
    {
        int[] output = new int[n+1];
        int[] count = new int[10];

        // Calculate count of elements
        for (int i = 0; i < n; i++)
            count[(a[i] / place) % 10]++;

        // Calculate cumulative frequency
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Place the elements in sorted order
        for (int i = n - 1; i >= 0; i--) {
            output[count[(a[i] / place) % 10] - 1] = a[i];
            count[(a[i] / place) % 10]--;
        }

        for (int i = 0; i < n; i++)
            a[i] = output[i];
    }
    // function to implement radix sort
    void radixsort (int a[], int n) {

        // get maximum element from array
        int max = getMax(a, n);

        // Apply counting sort to sort elements based on place value
        for (int place = 1; max / place > 0; place *= 10)
            countingSort(a, n, place);
    }
    // function to print array elements
    void printArray(int a[], int n) {
        for (int i = 0; i < n; ++i)
            System.out.print(a[i] + " ");
    }

    public static void main(String args[]) {
        int a[] = {432,8,530,90,88,231,11,45,677,199};
        int n = a.length;
        Day_35_RadixSort r1 = new Day_35_RadixSort();
        System.out.print("Before sorting array elements are - \n");
        r1.printArray(a,n);
        r1.radixsort(a, n);
        System.out.print("\n\nAfter applying Radix sort, the array elements are -\n");
        r1.printArray(a, n);
    }
}