Homework 5

Due: November 14th, 2012 at the beginning of class
Homework turned in after class will not be accepted.
Homework turned in during class but after I have collected it will lose 20%.

Do your own work for this assignment; do not work with others. Consult the book and your professor for help if you need it. Please write neatly, or preferably type your answers. Use good grammar, spelling, and complete sentences.

(20 points) Implement quicksort and bucket sort. Use the code in your book to help; the partition in quicksort is tricky. Make sure your implementations are correct — it is easy to gain some confidence in the correctness of your code by writing a program which creates arrays filled with random numbers, sorts them, and then checks that they are sorted.
Then time your code (using clock() or similar methods) on both methods for arrays filled with random integers of the following sizes (where n is the number of elements to be sorted, and m is the maximum integer value of the items in the input array):
1. n is very large, m is very small
2. n is very small, m is very large
3. Find values of n and m where both implementations take (approximately) equal time.
Discuss where quicksort performs best, and where bucket sort performs best.
A clock time of 0 isn't very meaningful. When timing your code, try doing the same thing many times (like 100 times or more) to get more accurate results. Show both your code and your results. Experiment with the values of m and n and with your code to get reasonable, interesting, reportable results.
Note that the quicksort code in the book is incorrect if you remove the dependence on insertionSort. If you include insertion sort, the code is correct. If you want to eliminate insertion sort, then you should do the following: surround line 27 in quicksort (the "restore pivot" step) with an if block:
```
            if ((right - left + 1) > 2) {
/* 27 */        swap(a[i], a[right - 1]); // Restore pivot
            }
```
Thanks to Jordan Willis for pointing out this bug.
(10 points) Write a program which, given an unsorted array of numbers, will print out the information that would allow us to sort the array (least-to-greatest) in one pass. This is the permutation that the original array is in, relative to its sorted order.
For example, if you were given the array A = [100, 50, 60, 250], then the permutation is P = [1, 2, 0, 3]. Then if we were to walk across this permutation, we could create the sorted array S by doing the following:
- S[0] = A[P[0]]
- S[1] = A[P[1]]
- S[2] = A[P[2]]
- S[3] = A[P[3]]
You may use a sorting algorithm to solve this problem. This is a hint!
(10 points) Do question 9.1 in your book.
(10 points) Do question 9.5 in your book.
(5 points) Do question 9.7 part (a) in your book.
(10 points) Do question 9.15 parts (a) and (b) in your book. Show each step of each algorithm for part (a).
(10 points) Do question 9.16 in your book.

valid html and css