Write a program in Java that performs the Counting Sort algorithm. a) Create the
ID: 3669759 • Letter: W
Question
Write a program in Java that performs the Counting Sort algorithm.
a) Create the countingSort method. Use the pseudocode shown in the lecture.
b) Test your codes by writing a program that uses the following input array: int[] array_A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2};
c) Your output should display the following versions of the arrays:
I. The original input array A
II. The counting array C after the counting (lines 4-5 in pseudocode) has completed
III. The counting array C after the summing (lines 7-8 in pseudocode) has completed
IV. The final sorted array B after performing the Counting Sort algorithm
Explanation / Answer
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
import java.lang.*;
import java.util.stream.*;
public class CountingSort {
void CS501HW5Q2_context() {
}
public static void main(String[] args) {
int[] A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2};
int[] B = new int[A.length];
int k = IntStream.of(A).parallel().max().getAsInt();
// int k = IntStream.of(A).max().getAsInt();// for performance comparision
long speedX = System.currentTimeMillis();
System.out.print(" A[]=");
IntStream.of(A).forEach(p -> System.out.print(p + ","));
System.out.println(" Max number in A[] is :" + k);
// System.out.println("A is of size :" + A.length);
B = countingSort(A, B, k);
System.out.println(" After coutingSort...");
System.out.print("B[]=");
IntStream.of(B).forEach(p -> System.out.print(p + ","));
System.out.println();
System.out.println("Time spent :" + (System.currentTimeMillis() - speedX));
}
void pseudo_countingSortInfo() {
}
void pseudo_countingSort() {
}
public static int[] countingSort(int[] A, int[] B, int k) {
int[] C = new int[k + 1];
System.out.print("C[]=");
IntStream.of(C).forEach(p -> System.out.print(p + ","));
System.out.print(" Start Counting...");
IntStream.of(A).parallel().forEach(p -> {
// System.out.print(p);
C[p]++;
});
System.out.print(" C[]=");
IntStream.of(C).forEach(p -> System.out.print(p + ","));
System.out.print(" Start Accumulating...");
IntStream.range(0, k + 1).forEach(p -> {
if (p > 0) {
C[p] = C[p] + C[p - 1];
}
});
System.out.print(" C[]=");
IntStream.of(C).forEach(p -> System.out.print(p + ","));
for (int j = A.length - 1; j >= 0; j--) {
B[C[A[j]] - 1] = A[j];
C[A[j]]--;
}
return B;
}
}
output
A[]=6,0,2,0,1,3,4,6,1,3,2,
Max number in A[] is :6
C[]=0,0,0,0,0,0,0,
Start Counting...
C[]=2,2,2,2,1,0,2,
Start Accumulating...
C[]=2,4,6,8,9,9,11,
After coutingSort...
B[]=0,0,1,1,2,2,3,3,4,6,6,
Time spent :45
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.