CS 201: Data Structures

Timing Sorting Algorithms

Partners: you may work alone or with a partner of your choosing

Just before midterm break, you timed several search structures on a spell-checking task, in hopes of getting insight into whether the theoretical running times of the various algorithms were consistent with your observations.

In this assignment, you'll do another round of timing, graphing, and discussing. This time, the subject will be a small collection of sorting algorithms: insertion sort, selection sort, mergesort, and heapsort. The first three are already implemented in Sorter.java. You'll have to implement heapsort yourself.

As before, please submit a short (no more than 3 pages) PDF document and any code you write. In the document, use timing data and whatever tools you deem appropriate to discuss whether your timing observations are consistent with the theoretical O/Ω/Θ bounds on each algorithm. Specifically, please address the following questions:

• Does selection sort act like a Θ(N²) algorithm? How can you tell?
• Does insertion sort act like a O(N²) algorithm? How can you tell?
• Insertion sort is Ω(N). Can you see this in real-life timing?
• Does mergesort act like a Θ(N*log(N)) algorithm? How can you tell?
• Does heapsort act like a Θ(N*log(N)) algorithm? How can you tell?
• Overall, how does selection sort perform in comparison to insertion sort?
• Overall, how does mergesort perform in comparison to heapsort?

Start early, ask questions, and have fun!