Instructions Write a program that performs a radix sort. The radix sort must als
ID: 3678151 • Letter: I
Question
Instructions Write a program that performs a radix sort.
The radix sort must also implement the counting sort. Your program must implement the sorting algorithms
Your program must sort the following lists:
List 1: 123, 3, 151, 234, 701, 181, 401, 924, 155, 233, 456, 735, 412, 6
List 2: 100, 191, 101, 192, 222, 245, 222, 235
List 3: MEL, TOD, TOM, JAC, CUB, KOB, KID, PLY, MIC, ABC
Your code MUST receive as input, your name and course section (CS4306, Sec 1) and output the following:
Your name: CS4306 Sec 1
Sorted list1
Sorted list2
Sorted list3
Your name
Important: Please don't forget the Output Screenshot!!
Explanation / Answer
import java.util.Arrays;
import java.util.Scanner;
public class RadixSort {
// do not instantiate
private RadixSort() { }
// The main function to that sorts String[] of size n using
// Radix Sort
public static void sort(String[] a, int W) {
int N = a.length;
int R = 256; // extend ASCII alphabet size
String[] aux = new String[N];
for (int d = W-1; d >= 0; d--) {
// sort by key-indexed counting on dth character
// compute frequency counts
int[] count = new int[R+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
// compute cumulates
for (int r = 0; r < R; r++)
count[r+1] += count[r];
// move data
for (int i = 0; i < N; i++)
aux[count[a[i].charAt(d)]++] = a[i];
// copy back
for (int i = 0; i < N; i++)
a[i] = aux[i];
}
}
// A utility function to get maximum value in arr[]
static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void sort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String name;
System.out.print("Enter you name and course section : ");
name = sc.nextLine();
int[] List1 = new int[]{123, 3, 151, 234, 701, 181, 401, 924, 155, 233, 456, 735, 412, 6};
int[] List2 = new int[]{100, 191, 101, 192, 222, 245, 222, 235};
String[] List3 = new String[]{"MEL", "TOD", "TOM", "JAC", "CUB", "KOB", "KID", "PLY","MIC", "ABC"};
sort(List1,List1.length);
sort(List2,List2.length);
sort(List3,3); // 3 is length of each string
System.out.println("Your Name: "+name);
System.out.print("Sorted list1: ");
for (int i = 0; i < List1.length; i++)
System.out.print(List1[i]+" ");
System.out.println();
System.out.print("Sorted list2: ");
for (int i = 0; i < List2.length; i++)
System.out.print(List2[i]+" ");
System.out.println();
System.out.print("Sorted list2: ");
for (int i = 0; i < List3.length; i++)
System.out.print(List3[i]+" ");
System.out.println();
}
}
/*
Output:
Enter you name and course section : CS4306 Sec 1
Your Name: CS4306 Sec 1
Sorted list1: 3 6 123 151 155 181 233 234 401 412 456 701 735 924
Sorted list2: 100 101 191 192 222 222 235 245
Sorted list2: ABC CUB JAC KID KOB MEL MIC PLY TOD TOM
*/