Question

Counting SortShow the B and C arrays after Counting Sort finishes on the array A [19, 6, 10, 7, 16, 17, 13, 14, 12, 9] if the input range is 0-19.

Answer 1

solution:

Given array A:

A

19	6	10	7	16	17	13	14	12	9
0	1	2	3	4	5	6	7	8	9

Range is given 0-19

Initialize an array C of length max+1 with all elements 0. This array is used for storing the count of the elements in the array.

C

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Store the count of each element at their respective index in array C.

C

0	0	0	0	0	0	1	1	0	1	1	0	1	1	1	0	1	1	0	1
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Store cumulative sum of the elements of the array C. It helps in placing the elements into the correct index of the sorted array.

C

0	0	0	0	0	0	1	2	2	3	4	4	5	6	7	7	8	9	9	10
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Add elements of array A to resultant array B.

B

0	0	0	0	0	0	0	0	0	0
0	1	2	3	4	5	6	7	8	9

Find the index of each element of the original array in the count array. This gives the cumulative count. Place the element at the index calculated.

For example: 19's count in the C array is 10 so it would be place at position 10-1 = 9 in the array B.

B

0	0	0	0	0	0	0	0	0	19
0	1	2	3	4	5	6	7	8	9

6's count in the C array is 1 so it would be place at position 1-1 = 0 in the array B.

6	0	0	0	0	0	0	0	0	19
0	1	2	3	4	5	6	7	8	9

Similarly, we can fill full array B as follows:

6	7	9	10	12	13	14	16	17	19
0	1	2	3	4	5	6	7	8	9

This the required sorted array.

Please give thumbsup, or do comment in case of any query. Thanks.