Assignment 5 Quick Sort

Purpose

To exercise one of the more efficient sorting algorithm. We are going to design the algorithm, test the program and measure its run-time performance for both average case and worst case in Big O notation.

Implementation

See course github for starter kit.

This assignment is to write a quicksort.cpp program based on the Pseudo Code Example on chapter 11.2.2, p.318 - 324. You are to implement a Quick Sort program based on the textbook example. This program have to trace the sorting of a random array in progress and its trace output needs to

Show all items of the array on a single trace line,

Each data exchange needs to be on a separate trace line, and

Show the active sorting range by placing an opening and a closing parenthesis around it.

Your program needs to run the quick sort only, i,e. sort the data using quick sort all the way through, from the begining to the end, Do not swtich to Insertion Sort as described in the textbook Although the Quick sort pivot selection is costly especially when the item numbers to sort is small. Therefore, the textbook example switch to selection sort when the item numbers in the segment to sort is less than 10. In this assignment, our main objective is to learn how this sort works, hence we are not going to fine tune the performance by switching to another basic sort, cheaper to setup when the item numbers in the segment to sort is below a certain threshold.

Here are the features need to be in your quick sort program:

Write C++ program based on this pseudo code in the textbook;

A the program start, show a predefined list (of your own) than before ;

Use the median-of-three (fist middle last) pivot selection.

Do NOT switch to a basic (selection) sort when the item numbers in the segment to sort is smaller than the threshold!

Stop the Quick Sort when the terminal case is reached, i.e. the segment to be sorted is less or equal to 2 items. If the number is 2, perform a simple swap if out of order. Otherwise, just return.

Display (prompt) the menu, defined in the User Interface below, after the start test and after the completion of a menu command;

Explain what and why for the worst case and average case of quick sort efficiency in Big O notation on the header of the quicksort.cpp;

Quick Sort Only In order to run the Quick Sort without calling the Insertion Sort, the main application listed in Program 11-5 (page 324) shall be modified as:

void quickSort(ItemType theArray[], int first, int last) { // Instead of switch to Selection Sort, handle the terminal case if(last - first  theArray[last]) swap(theArray[first] > theArray[last]); // Create the partition: S1 | Pivot | S2 int pivotIndex = partition(theArray, first, last); // Sort subarrays S1 and S2 quickSort(theArray, first, pivotIndex - 1); quickSort(theArray, pivotIndex + 1, last); } // end quickSort 

Terminal Case Here is a sample code for the case when the quicksort is only given two (MIN_SIZE) items to sort (i.e. terminal condition):

 if (last - first  theArray[last]) sswap(theArray[first], theArray[last]); } 

Show Trace Here is a sample code for the show() function above to show all the data exchange when it happened. This segment of code can be called where the array is accessible:

show(string theArray[], int first, int last) { for(int i=0; i 
 Quick Sort Performance In the textbook listed the performance of all sorting algorithms, In the prgram header you are going to identify the main factors that contribute to the run-time performance, for the average and worst case. The algorithm performance is expressed as the Big O notation. The common sorting performance are either O(n logn) or O(n^2). The two factors are the loop control mechanism used by the algorithm. You are to identify each of every contributing loop contorl logic's line # as well as why its performance is n or logn. Write this explaination as a comment on the file header. 
 
User Interface Use the following menu to drive this program.
 
Delimiter is ( , ) Trace is (ON or OFF) current list: current list with the delimiter  
 
 
 
n - New list s - quick Sort t - Trace mode d - Delimiter char q - Quit Enter your choice:  
 
The command options shall support:
 
user may enter a the delimited data line input of alpha numeric list;
 
user may "quit" from the program from menu;
 
user may change the default delimiter of list items from the menu to different single character;
 
user may turn on/off the trace flag which controls the proper print out to show the meaningful stages of sorting in progress.
 
 
 
Screen Capture  
 
Here is a screen capture for a test run on the example quick sort discussed in the class:
 
An example execution trace:
 
 
You are to use the parse function from the previous lab to parse an input delimited text string to tokens in a vector. Additional vector programming examples can be found in cplusplus.com (Links to an external site.)Links to an external site..
 
The Starter: 
 
Use the quicksort_starter.cpp from github. 
 
The user is expected to enter the entire collection (of test data) within one single line of delimited data.
 
Please also reference the textbook for quickSort implementation details.
 
Submit
 
(1) paper exercise
 
Quick Sort the folowing array. Use Median-of-three pivot selection, rtrace the Quick Sort instance by instance. Each QuickSort instance shall show the entire array before and after, step by step.
 
 (6,5,4,3,2,1,q,w,e,r)
 
An image of your simulation trace, similar to your quicksort program execution.
 
 
 
(2) Source file and excution validation
 
quicksort.cpp and appropriate validations.
 
As an example, the program should be able to produce the trace output when the TRACE option is enabled. Here is an example output:
  Running /home/ubuntu/workspace/comsc-210/m05/as5_merge_sort.cpp Delimiter is, Trace is ON Current List: 1 23 fds a n New List s Quick Sort t -Trace Mode d Delimiter Char h Help, this menu q- Quit Enter your choice: n Enter a comma delimited list of values: a,s,d,f,g,h,Y,T,R,E Enter your choice: s (a sd f g h Y T R E) (E T Y R a h dsf g) (E T Y R) a h dsf g (ERY T) a h dsf g (E) RY T a h dsf g E R(Y T) a h d s f g E R T Y a (h ds f g) E R T Y a (g d f h s) E R T Y a (g d f) h s E R T Y a (d f g) h s E R T Y a (d) f g h s E R T Y a d f (g) h s E R T Y a d f g h (s) Sorted List: E RTYadfgh s Enter your choice:  Running /home/ubuntu/workspace/comsc-210/m05/as5_merge_sort.cpp Delimiter is, Trace is ON Current List: 1 23 fds a n New List s Quick Sort t -Trace Mode d Delimiter Char h Help, this menu q- Quit Enter your choice: n Enter a comma delimited list of values: a,s,d,f,g,h,Y,T,R,E Enter your choice: s (a sd f g h Y T R E) (E T Y R a h dsf g) (E T Y R) a h dsf g (ERY T) a h dsf g (E) RY T a h dsf g E R(Y T) a h d s f g E R T Y a (h ds f g) E R T Y a (g d f h s) E R T Y a (g d f) h s E R T Y a (d f g) h s E R T Y a (d) f g h s E R T Y a d f (g) h s E R T Y a d f g h (s) Sorted List: E RTYadfgh s Enter your choice