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