CS1500
Algorithms and Data Structures for Engineering, Summer 1 2012
LAB 5: QuickSort
Implement a function QuickSort that sorts an array int A[MAX] using the quicksort algorithm. Obviously, you cannot use any C++ subroutine; you have to implement your own.
int QuickSort(int A[], int b, int e)
where b and e are the begin and end indexes determining the part of the array being sorted.
You can assume MAX is a globally defined variable, but you have to pass
the array as input to the function. Your function has to be recursive,
essentially executing the following:
- call Partition function: arrange the array so that all elements smaller than the pivot
come before the pivot, and all elements higher than the pivot come
after the pivot. Returns the pivot.
- recursively call the function QuickSort on the sub-array of elements up to the pivot
- recursively call QuickSort on elements after the pivot.
Here is a step by step Partition example.
EXTRA CREDIT: Implement a function that performs counting sort.
Verify that is faster than Quicksort empirically by keeping track (for
each routine) of the number of comparisons made; run both on a
large array, say like 100,000 elements randomly generated.