Description
Introduction
For this programming assignment you will implement Quick Sort and execute it with 4 separate data
sets. Each data set is a 1,000,000 element integer array, organized as follows:
random
nearly sorted ascending ( sorted ascending data set with small number of elements out of order)
sorted ascending
sorted descending
There are a number of different implementations of Quick Sort. Your implementation should start with the
pseudo coded Quick Sort algorithm presented in figure 3.5.1 of the zybook used for this course, with the
modifications that follow.
Add a call to System.nanoTime() immediately before, and immediately after the call to Quick Sort to
calculate how much time elapsed during the sorts. Output these values along with a description of
what’s being measured.
Median-of-Three Partitioning
The optimal choice for a pivot would be the median of the array. However, this is difficult to calculate and
would slow down Quick Sort significantly. One approach is to pick three elements randomly , and use
the median of these three as the pivot. As it turns out, the randomness doesn’t help much. So instead,
just use median of the first, last, and center elements as the pivot. For example, if you have the following
values for input:
17, 3, 9, 19, 13, 7, 11, 5, 15, 1
the first value is 17, the last value is 1, and the center value is 13. So in this case the pivot is 13.
Modify your implementation of Quick Sort to choose a pivot using Median-of-Three.
When the Sub-Arrays Get Small
Quick Sort is a recursive divide and conquer algorithm. As the recursive descent progresses, sooner or
later the sub-arrays will get small enough that Quick Sort doesn’t perform as well as other sorting
5/6/2020 Programming Assignment 2 – Quick Sort
https://lwtech.instructure.com/courses/1940982/assignments/18816756?module_item_id=43523009 2/2
algorithms. One possible remedy for this phenomenon is to switch to a sorting algorithms that is efficient
for small arrays.
Modify your implementation of Quick Sort to switch to Selection Sort when the length of a sub-array is
less than or equal to 20 elements.
Modify TestData.java
The current version of TestData.java (provided in this weeks Canvas Module) provides sorted ascending
data and random data. You will need to add two new methods to the class. One for generating sorted
descending data, and one for nearly sorted ascending data.
What to Turn In
When you have finished the assignment, upload your .java files to Canvas.
