Please do not change any of the method signatures in either class. Implement the methods described below. RadixSort.java RadixSort.java contains two different RadixSort implementations each using a different version of Counting Sort that you will implement. As a reminder the pseudocode for CountingSort discussed in class is as follows. countingSort(arr, n, k) 1. let B[1 : n] and C[0 : k] be new arrays 2. for i = 0 to k 3. C[i] = 0 4. for j = 1 to n 5 . C[arr[j]] = C [arr[j]] + 1 6. for i = 1 to k 7. C[i] = C[i] + C[i – 1] 8. for j = n downto 1 9. B[C[arr[j]]] = arr[j] 10 C[arr[j]] = C[arr[j]] – 1 11. return B private static void countingSort2(int[] arr, int k) Now you implement almost the same method, but instead of iterating from the end of arr, you will instead iterate from the beginning. So line 8 becomes for j=1 to n. You should think about why this alternative does not impact the correctness of CountingSort. You don’t need to write this down, just think about it. RadixSort2 is not working correctly even though your countingSort2 is working correctly1. Why is RadixSort2 not working? Write your answer in the location specified in RadixSort.java this is the method signature class: package sorting; import java.util.Arrays; public class RadixSort { //returns the max value in the array //used to provide the k to counting sort privatestaticint getMax(int[] arr) { intmax = Integer.MIN_VALUE; for(inti: arr) { if(i>max) max = i; } returnmax; } privatestaticvoid countingSort1(int[] arr, intplace) { int[] output = newint[arr.length]; int[] count = newint[10]; Arrays.fill(count, 0); /**********YOUR CODE GOES HERE***********/ // Count the frequency of each digit for (inti = 0; i < arr.length; i++) count[(arr[i]/place) % 10]++; // Calculate the cumulative count of each digit for (inti = 1; i < 10; i++) count[i] += count[i-1]; // Build the output array by placing the elements in their sorted position for (inti = arr.length-1; i >= 0; i--) { output[count[(arr[i]/place) % 10]-1] = arr[i]; count[(arr[i]/place) % 10]--; } //Reorder the original array using the output array for (inti = 0; i < arr.length; i++) arr[i] = output[i]; } publicstaticvoid radixSort1(int[] arr) { //Get the maximum to know how many digits I have intmax = getMax(arr); //Applies counting sort to each place starting with the 1s place for (intplace = 1; max / place > 0; place *= 10) countingSort1(arr, place); } privatestaticvoid countingSort2(int[] arr, intplace) { int[] output = newint[arr.length]; int[] count = newint[10]; Arrays.fill(count, 0); /**********YOUR CODE GOES HERE***********/ //Reorder the original array using the output array for (inti = 0; i < arr.length; i++) arr[i] = output[i]; } publicstaticvoid radixSort2(int[] arr) { //Get the maximum to know how many digits I have intmax = getMax(arr); //Applies counting sort to each place starting with the 1s place for (intplace = 1; max / place > 0; place *= 10) countingSort2(arr, place); /***********ANSWER QUESTION HERE*****************/ /* * Why is RadixSort2 not working? */ } }
Please do not change any of the method signatures in either class. Implement the methods described below.
RadixSort.java
RadixSort.java contains two different RadixSort implementations each using a different version of Counting Sort that you will implement. As a reminder the pseudocode for CountingSort discussed in class is as follows.
countingSort(arr, n, k)
1. let B[1 : n] and C[0 : k] be new arrays
2. for i = 0 to k
3. C[i] = 0
4. for j = 1 to n
5 . C[arr[j]] = C [arr[j]] + 1
6. for i = 1 to k
7. C[i] = C[i] + C[i – 1]
8. for j = n downto 1
9. B[C[arr[j]]] = arr[j]
10 C[arr[j]] = C[arr[j]] – 1
11. return B
private static void countingSort2(int[] arr, int k)
Now you implement almost the same method, but instead of iterating from the end of arr, you will instead iterate from the beginning. So line 8 becomes for j=1 to n. You should think about why this alternative does not impact the correctness of CountingSort. You don’t need to write this down, just think about it.
RadixSort2 is not working correctly even though your countingSort2 is working correctly1. Why is RadixSort2 not working? Write your answer in the location specified in RadixSort.java
this is the method signature class:
package sorting;
import java.util.Arrays;
public class RadixSort {
//returns the max value in the array
//used to provide the k to counting sort
privatestaticint getMax(int[] arr) {
intmax = Integer.MIN_VALUE;
for(inti: arr) {
if(i>max)
max = i;
}
returnmax;
}
privatestaticvoid countingSort1(int[] arr, intplace) {
int[] output = newint[arr.length];
int[] count = newint[10];
Arrays.fill(count, 0);
/**********YOUR CODE GOES HERE***********/
// Count the frequency of each digit
for (inti = 0; i < arr.length; i++)
count[(arr[i]/place) % 10]++;
// Calculate the cumulative count of each digit
for (inti = 1; i < 10; i++)
count[i] += count[i-1];
// Build the output array by placing the elements in their sorted position
for (inti = arr.length-1; i >= 0; i--) {
output[count[(arr[i]/place) % 10]-1] = arr[i];
count[(arr[i]/place) % 10]--;
}
//Reorder the original array using the output array
for (inti = 0; i < arr.length; i++)
arr[i] = output[i];
}
publicstaticvoid radixSort1(int[] arr) {
//Get the maximum to know how many digits I have
intmax = getMax(arr);
//Applies counting sort to each place starting with the 1s place
for (intplace = 1; max / place > 0; place *= 10)
countingSort1(arr, place);
}
privatestaticvoid countingSort2(int[] arr, intplace) {
int[] output = newint[arr.length];
int[] count = newint[10];
Arrays.fill(count, 0);
/**********YOUR CODE GOES HERE***********/
//Reorder the original array using the output array
for (inti = 0; i < arr.length; i++)
arr[i] = output[i];
}
publicstaticvoid radixSort2(int[] arr) {
//Get the maximum to know how many digits I have
intmax = getMax(arr);
//Applies counting sort to each place starting with the 1s place
for (intplace = 1; max / place > 0; place *= 10)
countingSort2(arr, place);
/***********ANSWER QUESTION HERE*****************/
/*
* Why is RadixSort2 not working?
*/
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
