Assignment 7 - Sorting

Due: Wednesday, May 28, at 10:00pm

Starter file: none
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

  • practice with sorting algorithms
  • practice thinking about performance of sorting algorithms

Collaboration policy

For this assignment, you may work alone or with a partner, but you must write up all of your answers yourself. (It is therefore unexpected for two submissions to be completely identical.) You may have at most one partner.

You may also discuss the assignment at a high level with other students. You can discuss the assignment with Tanya, our prefect, or any course staff.

You should list any student or course staff with whom you discussed the assignment (you don’t have to include prefect sessions), and the manner of discussion (high level, partner, etc.) in the reflection at the end of the assignment.

If you work alone, you should say so instead.

Assessment

To demonstrate proficiency, your submission needs to:

  • correctly answer questions 1-4
  • include a reflection at the end of your assignment

To demonstrate mastery, your submission needs to:

  • demonstrate proficiency
  • give thorough correct explanations for questions 5-7
  • include your collaboration statement in your response to the last question of the assignment

Assignment overview

The questions for this assignment are listed below. This is assignment does not require you to write any code.

You should complete this assignment on paper or a computer, but it needs to be in your own handwriting (not typed up). You will need to submit a PDF to Gradescope, and make sure to select the regions in your PDF that correspond to each solution – be sure to keep your answers somewhat separated from each other.

Proficiency questions

Complete the following questions to demonstrate Proficiency.

#1: Mergesort trace

On paper, sort the sequence of numbers 3, 1, 4, 1, 5, 9, 2, 6 using Mergesort. Be sure to show your work.

#2: Quicksort trace

On paper, sort the sequence of numbers 3, 1, 4, 1, 5, 9, 2, 6 using Quicksort. Assume you always select the pivot as the first element in the subarray, and be sure to show your work.

#3: Heapsort trace

On paper, sort the sequence of numbers 3, 1, 4, 1, 5, 9, 2, 6 using Heapsort. Assume you always select the pivot as the first element in the subarray, and be sure to show your work.

Don’t forget to build the initial heap using the heapify procedure we practiced in class!

#4: Fast sort

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 only use constant extra space.

Mastery questions

Additionally, complete the following questions to demonstrate Mastery.

#5: Quicksort pivot

The choice of pivot for Quicksort can dramatically affect its performance. Some common choices, relative to a given subarray, are:

  • the first element by position
  • the middle element by position
  • a randomly selected element
  • the median element by value
  • the median element of the first three elements

Comment on each of the above choices. What are the pros and cons of each? Under what situations are they good or bad ideas?

#6: Mergesort temp array

Look at the sample Mergesort code that was based on one of our readings.

One strange thing that it does is to pass in a temporary list as a parameter to the recursion. This seems silly; we could just create a temporary list inside the _mergesort function.

Explain why using a single temporary array, as in the sample code, can be argued to be an improvement over declaring one locally, either in terms of amount of memory needed, speed, or both.

#7: Heapsort coding

Suppose I asked you to code up Heapsort. (Alas, too many algorithms, not enough time…) At any rate, we’ve got an implementation of a heap already.

I can imagine two different approaches for Heapsort:

  1. Use the pre-existing heap code. Specifically: make an empty heap, 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 correctly from one end to the other as you go.

  2. Scrap the existing heap code, and write something similar that performs directly on the array that we have, using that array itself as the place for storing the heap.

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 advantage. Explain which choice above is the right one from a performance perspective, and explain why that is the case.

Reflection

Were there any particular issues or challenges you dealt with in completing this assignment? How long did you spend on this assignment?

Write a brief discussion (a sentence or two is fine) at the end of your assignment writeup.

Here are some examples:

  • Reflection:

I had forgot to swap the pivot into place in Quicksort, so I had to redo #2 a few times.

I had to refer to my notes to remember how to make a heap from an array

I spent 6 hours on this assignment.

  • Reflection:

I started late, so I had to rush my explanations.

I really don’t understand the difference in #7. I should probably go to office hours.

I spent 5 hours on this assignment.

  • Reflection:

This went fine; I forgot how the pivot worked in Quicksort but I found it in my notes.

I spent 3.5 hours on this assignment.