Question

Write code for A counting sort is a technique to sort an array of n positive integers that lie between 0 and m, inclusive. You need m + 1 counters. Then, making only one pass through the array, you count the number of times each integer occurs in the array. For example, the figure below shows an array of integers that lie between 0 and 4 and the five counters after a counting sort has made its pass through the array. From the counters, you can see that the array contains one 0, three 1’s, two 2’s, one 3, and three 4’s. These counts enable you to determine that the sorted array should contain [0, 1, 1, 1, 2, 2, 3, 4, 4, 4].

import java.util.Arrays;

public class Question4

{

/** Sorts an array of postive integers that lie within the range 0 to max.

@param a The array.

@param max The largest value in the array. */

public static void question4(int[] a, int max)

{

}

/*

* Do not write any code inside the main method and expect it to get marked.

* Any code that you write inside the main method will be ignored. However,

* you are free to edit the main function in any way you like for

* your own testing purposes.

*/

public static void main(String[] args)

{

int[] array = {2, 8, 4, 10, 15, 0, 4, 8, 2, 2, 0, 15, 10};

System.out.println("The array before sorting:");

System.out.println(Arrays.toString(array)); //must print [2 8 4 10 15 0 4 8 2 2 0 15 10]

question4(array, 15);

System.out.println("\nThe array after sorting:");

System.out.println(Arrays.toString(array)); //must print [0 0 2 2 2 4 4 8 8 10 10 15 15]

}

}

Answer 1

For this function we pass the array and the max value in the array i.e., 15. In the function, we create a counter array of size 1 more than the max value.

Then we fill this counter with the frequency of the number which is the current index. For eg current number is 2, then it will increment the value at index 2.

Finally using this counter, we put the index value in the array: a. For eg, for index i=0, the counter value is 2, so the 0 will be placed in the array at 0th place. Then counter value at that index is reduced as one instance of 0 is already placed.

CODE:

import java.util.Arrays;

public class Main{

public static void main(String[] args) {

  
int[] a = {2, 8, 4, 10, 15, 0, 4, 8, 2, 2, 0, 15, 10 };

System.out.println("Array before sorting:");
System.out.println(Arrays.toString(a));

question4(a, 15); //calling function to sort

System.out.println("Array after sorting:");
System.out.println(Arrays.toString(a));

}

public static void question4(int[] a, int max) {
int counter[] = new int[max + 1]; //creating m+1 sized counter
  
//filling the counter with number frequency
for (int i : a) {
counter[i]++;
}
  
// sort array
int x = 0;
for (int i = 0; i < counter.length; i++) {
while (0 < counter[i]) {
a[x++] = i; //put the index to the array
counter[i]--; //reduce counter at that index
}
}
}

}

OUTPUT: