Counting Sort

Computer Science Level 1

Given the array $A$ , during the counting sort algorithm, what does the $C$ array look like when it is first completed (before any modification)?

$A = [0,4,1,7,5,5,6,4,3,3,4,2,1,9,8,4,6]$

[1, 2, 1, 1, 3, 1, 2, 1, 1, 1]

[0,1,2,3,4,5,6,7,8,9]

[1,1,1,2,2,4,2,1,2,1]

[1, 2, 1, 2, 4, 2, 2, 1, 1, 1]

1 solution

Karleigh Moore
Jun 11, 2016

Relevant wiki: Counting Sort

The $C$ array keeps track of how many of each value there is in $A$ . Each index in $C$ corresponds to a value in $A$ . For example, the 0th index in $C$ will contain an integer that equals the number of times 0 appears in $A$ .

If we go through $A$ and count the number of each value, we get:

Number of 0's in $A$ = 1 Number of 1's in $A$ = 2 Number of 2's in $A$ = 1 Number of 3's in $A$ = 2 Number of 4's in $A$ = 4 Number of 5's in $A$ = 2 Number of 6's in $A$ = 2 Number of 7's in $A$ = 1 Number of 8's in $A$ = 1 Number of 9's in $A$ = 1

Therefore, $C = [1, 2, 1, 2, 4, 2, 2, 1, 1, 1]$ .

then why it's showing incorrect if i have selected 4th option.

shivam bhanu - 4 months ago

Counting Sort

1 solution

0 pending reports