Counting sort is a very efficient algorithm for sorting lists of integers into ascending order. Unlike algorithms like selection sort and insertion sort, which are general purpose algorithms that can be used to sort many different kinds of data, counting sort only works with integers. Further, counting sort only works with lists of integers where all the integers fall in a relatively small range.
For example, suppose we have a list of 1000 random integers that we need to sort. Suppose further that all of the integers to be sorted fall in the range from 0 to 99. To sort the list of integers we use a second array, the counts array. The counts array has size 100 and has a space to store a count for each integer from 0 to 99. At the start of the algorithm, we initialize all of the counts to 0. We then scan the array containing the 1000 integers and record how many times each integer in the original array appears. The simplest method for doing this is to examine the integers one at a time and increment the corresponding count in the counts array for each number we come to. For example, if the first entry in the array is the number 17, we would go to location 17 in the counts array and increment that count by 1. After scanning the array with the 1000 integers we will have collected the counts in the counts array. The final step is to replace the contents of the original array with a sorted list of numbers. We can do this by using the information in the counts array: if entry 0 in the counts array is, say, 15 we know we will need to place 15 0s at the beginning of the array. If the entry 1 in the counts array is 12, we would need to place 12 1s in the array.
Here is a simple example of counting sort. Here is a list of 15 integers, where no integer is smaller than 0 and no integer is larger than 5.
3 3 0 2 1 4 0 4 5 2 5 3 1 3 1
Here is the counts array for this list.
| n | count |
|---|---|
| 0 | 2 |
| 1 | 3 |
| 2 | 2 |
| 3 | 4 |
| 4 | 2 |
| 5 | 2 |
Using the information in the counts array, we can construct the sorted list:
0 0 1 1 1 2 2 3 3 3 3 4 4 5 5
Write a program that implements the counting sort algorithm. Your program should determine the largest integer in the original list and use that information to size the counts array accordingly.
You are welcome to use my insertion sort program as a starting point for your work on this assignment. Simply replace the insertionSort method in that program with a countingSort method. That program also provides useful code for filling an array with random integers, printing the array, and timing how long it takes to execute the sorting algorithm.
This assignment is due on Wednesday, April 29.