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 in Python, which is from another textbook. The code is very clean and well-written: even if you are unfamiliar with Python, it should be quite readable. The code that we wrote in class uses considerably less memory, though. Explain why. Furthermore, provide an estimate in terms of n (the size of the array) of how much memory our approach uses in comparison with the textbook approach.
   
   If you are unfamiliar with Python, the slicing operators might be confusing. Here is a quick tutorial on Python lists that shows how lists (also known as arrays) work in Python, including slicing.
   
   The point of this question is not to decipher subtle differences between Python and Java, so don't go chasing down that route. There's something pretty fundamentally different from our in-class example in how this Python code uses memory.

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 completely miss the the critical point, however, that indicates what the right choice is. Explain whether choice a or b above is the right one, and explain what the important reason is.