Homework 2 (5pt. + extra 1pt.)
Submission instruction:
Submit one single pdf file for this homework including both coding problems and analysis problems.
For coding problems, copy and paste your codes. Report your results.
For analysis problems, either type or hand-write and scan.
Question 1 (2 pt.) Randomized Quicksort: Write codes for randomized quicksort. You may need rand()
to generate random numbers. Run the randomized quicksort 5 times for input array A = {1, 2, 3, …, 99,
100} and report the 5 running times.
Question 2 (2pt.) Heapsort: Write codes for heapsort. The input array is a random permutation of A={1,
2, 3, …, 99, 100}. You should write codes to generate and print the random permutation first.
Question 3 (1pt.) Counting Sort: Write codes for counting sort. The input array is A = {20, 18, 5, 7, 16,
10, 9, 3, 12, 14, 0}.
Question 4 (extra 1pt.) Radix Sort: Write codes for radix sort: use counting sort for decimal digits from
the low order to high order. The input array is A = {329, 457, 657, 839, 436, 720, 353}.
