Questions on Sorting

This assignment is to be done individually, without a partner. You may share ideas with others in the class, but you should turn in your own assignment. Turn in your answers electronically.

1. On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using merge sort.
2. On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using quicksort with the pivot in the first position.
3. Suppose that you have an array of n elements, containing only two distinct keys, true and false. Give an O(n) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space.
4. The choice of pivot for quicksort can dramatically affect its performance. Some common choices are:
   • The first element
   • The middle element
   • A randomly selected element
   • The median element of the array
   • The median element of the first three elements in the array
   Comment on each of the above choices. What are the pros and cons of each? Under what situations are they good or bad ideas?
5. Look at this code for merge sort. It's similar to the code in the textbook, but I've coded it myself. It is without generics to make it a little easier to read. There's one major difference in how it is structured from some versions that can sometimes be found, in that my code makes use of a single temporary array, passed in as a parameter, insted of creating two half-size arrays in the merge method. Explain why my approach of using a single temporary array can be argued to be an improvement over the version on the linked page above, either in terms of amount of memory needed, speed, or both.

6. Suppose I asked you to code up heapsort. (Too many algorithms, not enough time, sniff...) At any rate, we've got a wonderful implementation of a heap already. I can imagine two different approaches for heapsort:

   a. Use the pre-existing heap code. Specifically: make a heap object, then loop over your array of data that you need to sort, and add each item to the heap. Then remove items from the heap, one at a time, filling up the array from the left to the right as you go (since the heap code we implemented is a min-heap).

   b. Scrap the existing heap code, and write something similar that performs directly on the array we have.

   An argument for the first choice might go something like: "We've got this pre-existing code, we should use it. Leveraging pre-existing code is smart." An argument for the second choice might go something like "We want our heapsort code to be clear and concise, and we're not using it as a general purpose heap. We should write our code to specifically target our purpose. For example, we don't need to be able to add items to the heap once we start removing them." Both of these arguments are about style, which is worthwhile, but one of these approaches may have a significant performance gain. Explain whether choice a or b above is the right one from a performance perspective, and explain why that is the case.