Question: void countingSort(int A[1...n], int k) 1: //Precondition: The n values in A are all between 0 and k 2: Let C[0... k] be a new

 void countingSort(int A[1...n], int k) 1: //Precondition: The n values in

void countingSort(int A[1...n], int k) 1: //Precondition: The n values in A are all between 0 and k 2: Let C[0... k] be a new array 3: //We will store our sorted array in the array B. 4: Let B[1...n] be a new array 5: for i = 0 to k do 6: C[i] = 0: 7: end for 8: for i = 1 to n do 9: C[A[i]] = C[A[i]] + 1: 10: end for 11: //C[i] now contains the # of elements in A equal to i 12: for i = 1 to k do 13: C[i] = C[i] + C[i - 1]: 14: end for 15: //C[i] now contains the # of elements in A that are lessthanorequalto to i 16: for i = n down to 1 do 17: B[C[A[i]]] = A[i]: 18: C[A[i]] = C[A[i]] - 1: 19: end for 20: return B: Illustrate the operation of countingSort ({2, 1, 5, 3, 1, 2, 5}, 6). Specifically, show the changes made to the arrays A, B, and C for each pass through the for loop at line 16

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!