CISC220 Program 3: New and Improved QuickSort

Due Tuesday, July 28 at 11:59pm

Write an industrial-strength quicksort function with the following enhancements:

A: If an array segment contains 20 elements or fewer, sort it using insertion sort.

B: After sorting the first, middle, and last elements (using bubblesort), use the median as a pivot, instead of swapping the median with the first element. (Save this value in Pivot_val). Because the first and last elements are in the correct partitions, it is not necessary to test them before advancing up and down. This is also the case after each exchange, so increment up and decrement down at the beginning of the do…while loop. Also, it is not necessary to test whether up is less than last before incrementing up, because the condition pivot_val < *up is false when up equals last-1 (the median must be >= the last element in the array).

Files you will be given:

TestSorts.cpp (do not modify)

InsertionSort3.h (must be modified)

QuickSort3.h (must be modified)

Random.h (do not modify)

Makefile (use at your own discretion).

You will have to modify QuickSort3.h and InsertionSort3.h to follow the above specifications. TestSorts.cpp and Random.h are already written and does not need to be modified.

In addition, you will have to write BubbleSort3.h from scratch.

To turn in:

This project is due at midnight, on Tuesday, July 28. It is advised that you start early and mail questions as you go.

You should turn in the usual stuff: Anything you modified, a script file of TestSorts.cpp run on at least 5 arrays of different lengths (try large lengths to see the greatest savings), a ReadMe file explaining what you’ve done, and the makefile.