Quick Sort
QuickSort is one of the fastest and most well-known sorting algorithms. QuickSort is a divide and conquer algorithm that relies on comparisons of elements.
QuickSort Algorithm
- If the number of data items (N) is one then return the sorted list
- Otherwise partition the data items based upon a "split value" so that every item with a lower index in the list is less than or equal to the split value and every item with a higher index is greater than the split value.
- Sort the two sublists using QuickSort
void QuickSort(int A[], int TopIndex) where A is a list of integers.
As you might have deduced from the code above most of the work is done in the Partition operation. Therefore we will create a function called Partition that will partition a list into two lists such that every element in the first list is less than every element in the second list. A split location (index) separates the two lists. (It is actually the highest index in the first list.)
int Partition(int A[])
splitLoc is the index of A such that A[i] <= A[j] whenever i <=splitLoc and j > splitLoc.
Partition returns the split location.
Our driver program will, basically, generate a dataset of a certain size and then call QuickSort to sort the data. We will need several utility functions to do basic work like print out the results of the sort and to check to make sure the data is actually sorted.
void DisplayData(float DataArray[], int TopIndex);
bool CheckSorted(float DataArray[], int TopIndex);
The final program should do the following:
- Explain its purpose to the user
- Ask the user for the number of numbers to be sorted
- Generate a single random data set
- Sort the data
- Report the size of the dataset and the time required to sort or the number of comparisons or both.
Here is a QuickSort skeleton and pseudocode to give you additional help if needed.
As always the base grade for this assignment is a B+.
A good extra credit enhancement would be to ask the user how many trials he/she would like and execute the program that many times with that many data sets and write the results to a file. This will enable us to compare the running times with respect to the size of the input.
Top of this page 
Home page 
