Counting, Radix and Bubble sorts

1)Illustrate the operation of Counting-Sort on the array A={6,0,2,0,1,3,4,6,1,3,2}

2)Illustrate the operation of Radix-Sort on the following list of English words: COW,DOG,SEA,RUG,ROW,MOB,RAT,BAT,BAR,EAR,TAR,DIG,BIG,TEA,NOW,FOX}.

3)Illustrate the operation of Bucket Sort on the array A={.81,.09,.13,.61,.43,.23,.98,.60,.75,.41}.

4)Explain how to sort n integers in the range 0 to n^2-1 in O(n) time.

5)Which of the following sorting algorithms are stable: insertion sort,merge sort,heapsort and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does the scheme take?

6)What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(nlgn)?

7)Describe an algorithm that, given n integers in the range 0 to k,preprocesses its input and then answers any query about how many of the n integers fall into a range [a...b] in O(1) time.The algorithm should use THETA(n+k) preprocessing time.

8)When are Radix and Bucket sorts used?