Question

Radix sortCome up with an unsorted array of numbers (integer array). Sort the numbers in ascending order and descending order and display them using radix sort. First sort in ascending, then reset the array to its original order and finally sort the array again in descending order. I need this in java language. Radix Sort assignment (CISP430 ignore this part) This is only for those who are using Java How many classes do I need? A: Node, Queue, Radix, Driver Do not use any of the built-in data structures What goes into the Radix class A: There are a couple of ways to do this. You can deal with instances or you can make everything in this class static. The static approach makes the most sense For the static approach, you can simply call a static method inside the Radix class as such Radix.sort(arr); where arr represents the array to be sorted. This function can return a sorted array. The sort method can call helper functions so that it doesn’t become too long. Where should I put the functions that display the array in ascending and descending order? A: It is up to you. This can be done in the Driver Class or it can be done in the Radix class General: Why do I need a queue A: You need an array of queues( from 0-9) which correspond to all the possible digits.For example queue[0] will hold all the numbers that contain a zero in the spot that corresponds to the pass that you are on. For example, let’s say we have 120, 30,41 For pass 1, Queue[0] would contain 120 and 30 Queue[1] would contain 41 Notice on the 1st pass, we are processing the 1st digit from the right and on each subsequent pass, we would work our way to the right one digit at a time. To display in descending order, can I just display the array backwards A: yes Do I worry about negative numbers? A: You don’t have to incorporate negative numbers for this lab Where do I define my array and how big does it have to be? A: You can hardcode your array in your program and make it as big or small as you want it.

Answer 1

The java code for radix sort is:

public class radixSort{
        static void occur_ascending(int arr[], int n, int j)
        {
                int temp[] = new int[n];
                int count[] = new int[10];
                for (int i = 0; i < n; i++) // no. of occurrences is stored
                        count[(arr[i] / j) % 10]++;
                for (int i = 1; i < 10; i++)
                        count[i] += count[i - 1];
                for (int i = n - 1; i >= 0; i--) {
                        temp[count[(arr[i] / j) % 10] - 1] = arr[i];
                        count[(arr[i] / j) % 10]--;
                }
                for (int i = 0; i < n; i++) // store the modified array after sorting according to digit's place
                        arr[i] = temp[i];
        }
        static void occur_descending(int arr[], int n, int j)
        {
                int temp[] = new int[n];
                int count[] = new int[10];
                for (int i = 0; i < n; i++) // no. of occurrences is stored
                        count[9-(arr[i] / j) % 10]++;
                for (int i = 1; i < 10; i++)
                        count[i] += count[i - 1];
                for (int i = n - 1; i >= 0; i--)
                        temp[--count[9-(arr[i] / j) % 10]] = arr[i];
                for (int i = 0; i < n; i++) // store the modified array after sorting according to digit's place
                        arr[i] = temp[i];
        }
        public static void main(String[] args)
        {
                int arr1[] = {23, 56, 9, 198, 30, 1, 5203, 601}; // random array given as input
                int n = arr1.length; // length of array is found
                int a = arr1[0]; // maximum element of array is found
                for (int i = 1; i < n; i++)
                        if (arr1[i] > a)
                                a = arr1[i];
                for (int j = 1; a / j > 0; j *= 10)
                        occur_ascending(arr1, n, j);
                for (int i = 0; i < n; i++)
                        System.out.println(arr1[i]);
                System.out.println("");
                int arr2[] = {23, 56, 9, 198, 30, 1, 5203, 601}; // random array given as input
                n = arr2.length; // length of array is found
                a = arr2[0]; // maximum element of array is found
                for (int i = 1; i < n; i++)
                        if (arr2[i] > a)
                                a = arr2[i];
                for (int j = 1; a / j > 0; j *= 10)
                        occur_descending(arr2, n, j);
                for (int i = 0; i < n; i++)
                        System.out.println(arr2[i]);
        }
} 

The sample of the code is:

The output of the code is:

I have ignored the part you have mentioned in the above question.