A counting sort is a simple way to sort an array of n positive integers that lie between

Chapter 9, Problem 11

(choose chapter or problem)

A counting sort is a simple way 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, Figure 9-12 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 1s, two 2s, one 3, and three 4s. These counts enable you to determine that the sorted array should contain 0 1 1 1 2 2 3 4 4 4. a. Write a method that performs a counting sort. b. How does the efficiency of a counting sort compare to that of an insertion sort or a quick sort? FIGURE 9-12 A counting sort of an array (see Exercise 11) Original array 4 2 1 3 4 1 2 1 0 4 One 0 Three 1s Two 2s One 3 Three 4s 3 3 4 2 1 1 2 1 3 0 Counters Sorted array 0 1 1 1 2 2 3 4 4 4