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:
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.