[Homework 5 is due on Aug 5 at 11:59pm]

Problem: [Sorting contest] Choose and implement any three sorting algorithms (working on an array of integers), with one selection taken from each group presented below, and establish empirically which is the best sorting algorithm among them (in terms of time taken to sort large arrays).

Group 1 [Worst case complexity: Θ(n2)]

  • Selection Sort
  • Insertion Sort

Group 2 [Worst case complexity: Θ(n log n)]

  • Heapsort
  • Mergesort
  • Splay tree sort

Group 3 [Worst case complexity: Θ(n2); Average case complexity: Θ(n log n)]

  • Quicksort (with randomized or median-of-3 pivot selection)

The starter files are here. Things that are left for you:

1. Implement three of the chosen sorting algorithms.  The corresponding header files are already there. For example, if you choose to implement Merge Sort, your implementation should go into MergeSort.h. I have already provided the implementations of Exchange Sort in ExchangeSort.h and BST Sort in BSTSort.h as samples.

2. [Already provided] Introduce a time check wrapper around the call to each sorting algorithm. In order to further simplify your work, I have modified main.cpp to have the timing wrappers.

3. [Bonus] (a) Vary the inputs and come up with a graphical comparison between the chosen sorting algorithms. (b) Also, for fun, feel free to add a poor quality pivot selection (with first element chosen as the pivot) in Quicksort to see the result. To accomplish this, you can add another file called PoorQuickSort.h, where PoorQuickSort will inherit from SortingAlgorithm. In main.cpp, add the necessary instantiation of PoorQuickSort and timing wrappers.

Write a short report on your finding and submit that along with the source code changes.

Expected output: If implemented properly, you should get the following trend of numbers.

Exchange Sort: 35376
Heap Sort: 909
Insertion Sort: 12385
Merge Sort: 578
Quick Sort: 358
Poor Quick Sort: 5963
Selection Sort: 10809
Binary Search Tree Sort: 15691
Splay Tree Sort: 272