C <- an array of 10 integers all initialized to zero B <- an array of n numbers (this will be the output array) for each i from 0 to n-1 do // After this, C[x] is the number increment C[A[i]] // of times x appears in A. for each i from 1 to 9 do // After this, C[x] is the number of elements C[i] <- C[i] + C[i-1] // of A that are less than or equal to x. for each i from n-1 downto 0 do B[C[A[i]] - 1] <- A[i] C[A[i]] <- C[A[i]] - 1The array B then holds the original elements in sorted order.
A = [3 1 8 0 8 0 1 0 3 8]all of whose entries lie in the range [0..9]. This is a candidate for counting sort! What does the array C look like after the first loop? What does the array C look like after the second loop? What does the array B look like after 7 iterations through the last loop?
Turn in: A "picture" of the array C after the first loop. A "picture" of the array C after the second loop. A "picture" of the array B after 7 iterations through the third loop (any uninitialized entries in B should be marked with an "x").
Turn in: A paragraph explaining how you derived the time complexity of Counting Sort. (And yes, actually state that complexity!)
______ n! = \/2 Pi n (n/e)^n (1 + (1/n))From Stirling's Approximation you can prove that
lg(n!) = (n lg n)