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. 
 
Here is the starter code:
 
#include 
 
#include 
 
#include  // container
 
#include  // menu
 
#include  // qsort
 
 
 
#define under "\33[4m"
 
#define over "\33[0m"
 
 
 
// example cout  
 
 
 
 
using namespace std;
 
 
 
static const int MIN_SIZE = 2; //smaller use swap
 
char delimiter = ',';
 
bool trace = false;
 
 
 
void showTrace(vector& arr, int first, int last, int pivotIndex);
 
void show(vector& arr);
 
int comp(const void *one, const void *two);
 
void order(vector& arr, int i, int j);
 
void sortFirstMiddleLast(vector& arr, int first, int last);
 
int partition(vector& arr, int first, int last);
 
void quickSort(vector& arr, int first, int last);
 
 
 
int main() {
 
 cout  
 vector a={9,7,3,5,6,8,2};
 
 
 
 cout  
 for(auto item:a) cout  
 cout  
 
 
 // Try lambda for local meaning
 
 auto acomp = [] (const void* a, const void* b) 
 
 {return ( (a > b)?1:( (a==b)?0:-1) );};
 
 
 
 vector demo(a);
 
 qsort(&demo[0], demo.size(), sizeof(int), acomp);
 
 cout  
 for(auto item:demo) {
 
 cout  
 }
 
 cout  
 
 
 vector ar = {"9","7","3","5","6","8","2"};
 
 
 
 auto menu = [&] () {
 
 cout  
  
 show(ar);
 
 cout  
  
  
  
  
 
 
 menu( );
 
char choice; // user choice of command
 
 do {
 
 cout  
  
  
cin >> choice;
 
cin.ignore(1000, ' ');
 
choice = tolower(choice);
 
string input, token;
 
vector test(ar);
 
stringstream ss;
 
switch(choice) { // main menu switch starts
 
case 'n': // new
 
cout  
getline (cin, input);
 
 ss  
 ar.clear();
 
 while(getline(ss, token, delimiter))
 
 ar.push_back(token);
 
break;
 
case 't': 
 
 trace = !trace;
 
 break;
 
 case 'd': // delimiter
 
 cout  
 cin >> delimiter;
 
 break;
 
 case 's':
 
 // quickSort(test, 0, test.size() - 1);
 
 cout  
 show(test);
 
 cout  
 break;
 
 case 'm':
 
 menu();
 
 break;
 
 case 'q':
 
 break;
 
default:
 
 cout  
}
 
 } while (choice!='q');
 
}
 
 
 
// void quickSort(vector& arr, int first, int last)
 
// {
 
// }
 
 
 
void sortFirstMiddleLast(vector& arr, int first, int last) {
 
 int middle = (first + last)/2;
 
 order(arr, first, middle);
 
 order(arr, middle, last);
 
 order(arr, first, middle);
 
}
 
 
 
// int partition(vector& arr, int first, int last){
 
// }
 
 
 
int comp(const void *one, const void *two) {
 
 int a = *((int*)one);
 
 int b = *((int*)two);
 
 if (a 
 if (a == b) return 0;
 
 return 1; 
 
}
 
 
 
void show(vector& arr) {
 
 string output; // how does this one work?
 
 for(auto item:arr) {
 
 if (!output.empty()) output += ",";
 
 output += item; 
 
 }
 
 cout  
}
 
 
 
 
 
void showTrace(vector &arr, int first, int last, int p) {
 
 for(int i=0; i 
cout  
  
  
}
 
 cout  
}
 
 
 
void order(vector& arr, int i, int j) {
 
if (arr[i] > arr[j])
 
std::swap(arr[i], arr[j]); 
 
} 
 
 
 
 
  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