Write a Java program to implement the radix sort The sort sh

Write a Java program to implement the radix sort. The sort should be able to handle both even and odd sized lists. Use randomly generated integers between 1 and 9999. Display the list after each iteration of the “radix”.

Solution

import java.util.Scanner;
import java.util.Random;

/** Class RadixSort **/
public class RadixSort{

/** Radix Sort function **/
public static void sort(int[] arr){
        if(arr.length == 0)
            return;
        int[][] np = new int[arr.length][2];
        int[] q = new int[0x100];
        int i,j,k,l,f = 0;
        for(k=0;k<4;k++){
            for(i=0;i<(np.length-1);i++)
                np[i][1] = i+1;
            np[i][1] = -1;
            for(i=0;i<q.length;i++)
                q[i] = -1;
            for(f=i=0;i<arr.length;i++){
                j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
                if(q[j] == -1)
                    l = q[j] = f;
                else{
                    l = q[j];
                    while(np[l][1] != -1)
                        l = np[l][1];
                    np[l][1] = f;
                    l = np[l][1];
                }
                f = np[f][1];
                np[l][0] = arr[i];
                np[l][1] = -1;
            }
            for(l=q[i=j=0];i<0x100;i++)
                for(l=q[i];l!=-1;l=np[l][1])
                        arr[j++] = np[l][0];
          
            for (int ii = 0; ii<arr.length; ii++){
                System.out.print(arr[ii]+\", \");
            }
            System.out.println(\"\");
        }
    }

    /** Main method **/
    public static void main(String[] args){
        Scanner scan = new Scanner( System.in );
        System.out.println(\"Radix Sort Test\ \");
        int n;
        /** Accept number of elements **/
        System.out.print(\"Enter number of integer elements: \");
        n = scan.nextInt();
        /** Create integer array on n elements **/
        int arr[] = new int[n];
        /** Accept elements **/
        Random rand = new Random();
        for (int i = 0; i<n; i++){
            arr[i] = rand.nextInt(9999)+1;
        }
        /** Call method sort **/
        sort(arr);
        /** Print sorted Array **/
        System.out.println(\"\ Elements after sorting \");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+\" \");
        System.out.println();
    }
}