Illustrate the operation of counting Sort ({2, 1, 5, 3, 1, 2, 5},6). Specifically, show the...

   

Transcribed Image Text:

Illustrate the operation of counting Sort ({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. Algorithm 1 int counting Sort (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 ton do 9: C[A[i]] = C[A[i]] + 1; 10: end for 11: //C] now contains the # of elements in A equal to i 12: for 13: 1 to k do Ci] C[i]+C[i-1]; 14: end for 15: //C[] now contains the # of elements in A that are < to i 16: for in down to 1 do 17: 18: B[C[A[i]]] = A[i]; C[A[i]] = C[A[i]] - 1; 19: end for 20: return B; Illustrate the operation of counting Sort ({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. Algorithm 1 int counting Sort (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 ton do 9: C[A[i]] = C[A[i]] + 1; 10: end for 11: //C] now contains the # of elements in A equal to i 12: for 13: 1 to k do Ci] C[i]+C[i-1]; 14: end for 15: //C[] now contains the # of elements in A that are < to i 16: for in down to 1 do 17: 18: B[C[A[i]]] = A[i]; C[A[i]] = C[A[i]] - 1; 19: end for 20: return B;