Recall the counting sort algorithm, where 1 n is the number of elements to be so

Question

Recall the counting sort algorithm, where

1    n is the number of elements to be sorted

2    each element is an integer in the range 1 tok

3    A is the input array, of size n

4    B is the final sorted output array

5    C is the intermediate array of size k

1: for i = 1 to k

2:     C[i] = 0

3: for i = 1 to n

4:     C[A[i]] = C[A[i]] + 1

5: for i = 2 to k

6:     C[i] = C[i] + C[i-1]

7: for i = n downto 1

8:     B[C[A[i]]] = A[i]

9:     C[A[i]] = C[A[i]] - 1

(a) For the input array [6,3,7,5,4,3,3,2,8,9,1,6], and k = 9,specify the contents of

      the arrays B and C

• (4 points) after the second for-loop (line 3); C =

• (2 points) after the third for-loop (line 5); C =

   B =
C =
2. (3 points)

B =
C =
3. (3 points)
B =
C =
(b) (5 points) Suppose that the for-loop on line 7 above, ismodified as follows:
7: for i = 1 to n

Will the algorithm still sort the input? If no, explain why not. Ifyes, what is the effect of this
Modification to the algorithm and the output?

Explanation / Answer

Recall the counting sort algorithm, where

1    n is the number of elements to be sorted

2    each element is an integer in the range 1 tok

3    A is the input array, of size n

4    B is the final sorted output array

5    C is the intermediate array of size k

1: for i = 1 to k

2:     C[i] = 0

3: for i = 1 to n

4:     C[A[i]] = C[A[i]] + 1

5: for i = 2 to k

6:     C[i] = C[i] + C[i-1]

7: for i = n downto 1

8:     B[C[A[i]]] = A[i]

9:     C[A[i]] = C[A[i]] - 1

(a) For the input array [6,3,7,5,4,3,3,2,8,9,1,6], and k = 9,specify the contents of

      the arrays B andC  

• (4 points) after the second for-loop (line 3); C=   1,1,3,1,1,2,1,1,1

• (2 points) after the third for-loop (line 5); C=   1,2,4,5,6,8,9,10,11

   B = -,-,-,-,-,-,-,6,-,-,-,-
C = 1,2,4,5,5,8,9,10,11
2. (3 points)

B =1,-,-,-,-,-,-,6,-,-,-,-
C = 0,2,4,5,5,8,9,10,11

3. (3 points)
B =1,-,-,-,-,-,-,6,-,-,8,-
C = 0,2,4,5,5,8,9,10,10
(b) (5 points) Suppose that the for-loop on line 7 above, ismodified as follows:
7: for i = 1 to n

Will the algorithm still sort the input? If no, explain why not. Ifyes, what is the effect of this
Modification to the algorithm and the output?

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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