Most sorting algorithms work by directly comparing the values to be sorted. This

Question

Most sorting algorithms work by directly comparing the values to be sorted. This is
intuitive, but there is a lower bound on how efficient these algorithms can be. A slightly
more efficient sorting algorithm that works without comparisons is called counting sort.
Counting sort works as follows: we count the number of times each unique value occurs
in the unsorted data set. For example, we count the number of 1's, 2's, 3's, etc. Then we
generate the sorted data set by creating the appropriate number of copies of each
value. For example, if we counted three 4's in the unsorted data, we would add three 4's
to the sorted data set.
Put another way, if we have an array of integers that are in the range 0 to n, we create a
second array of n+1 elements to count the number of occurrences of each integer in the
array. For example, if the array contained 5 occurrences of 23, count[23] would contain
the value 5.
To generate the sorted array, we run through the array from count[0] to count[n-1].
For each element of count, we fill that many spaces in the sorted array with the index
of the element. For example, if count[1] held the value 3, the first three elements of the
sorted array would be 1 (assuming that our integer range is from 0 to n).
As an example, consider the following array of 9 integers in the range 0 to 5:
[2, 3, 2, 1, 4, 5, 2, 3, 1]
The count array would contain the following values:
[0, 2, 3, 2, 1, 1]
Working from this set of counts, the sorted array would be:
[1, 1, 2, 2, 2, 3, 3, 4, 5]
Counting sort has the unfortunate property of destroying (and recreating) the original
data set, which is why it can only be used for integer values. However, it is very fast
when you only need to sort integers.
Write a small Java program that does the following:
1. Prompts the user to enter a positive integer n. Your program will sort a list of integers
in the range 0–n.
2. Randomly generates a list of 100 integers in the specified range. Use the Random
class to do this; we discussed this Java class in lecture.
3. Prints the unsorted list to the screen.
4. Uses counting sort to sort the data set. Write a separate countingSort() method
to do the sorting and return a sorted version of the data set; don't do the
sorting directly in main()!
Your countingSort() method should take n and the unsorted array as its
arguments. Inside countingSort(), do the following:
a. Create an integer array to hold n+1 elements
b. Use a loop to count the number of times each value appears in the unsorted array
c. Create a new integer array to hold the sorted values
d. Use a nested loop to fill the sorted array: for each element of the count array, use
a loop to add that many copies of the element to the sorted array.
e. Return the sorted array
5. Prints the sorted data set to the screen.

Explanation / Answer

import java.util.Arrays;

import java.util.Random;

import java.util.Scanner;

public class CountSort {

       public static void main(String[] args) {

              Scanner in = new Scanner(System.in);

              int n = 0;

              while(n <= 0) {

                     System.out.print("Enter a positive integer: ");

                     n = in.nextInt();

              }

              int arr[] = new int[100];

              Random rand = new Random();

              for(int i = 0; i < 100; ++i) {

                     arr[i] = rand.nextInt(n+1);

              }

              System.out.println("Original Array: " + Arrays.toString(arr));

              int newArr[] = countingSort(n, arr);

              System.out.println("Sorted Array: " + Arrays.toString(newArr));

       }

       private static int[] countingSort(int n, int arr[]) {

              int count[] = new int[n+1];

              for(int i = 0; i < arr.length; ++i) {

                     count[arr[i]]++;

              }

              int newArr[] = new int[arr.length];

              int index = 0;

              for(int j = 0; j < count.length; ++j) {

                     for(int k = 0; k < count[j]; ++k) {

                           newArr[index] = j;

                           ++index;

                     }

              }

              return newArr;

       }

}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.