/********************************************
 * RICHARD MENDLER                          *
 *                                          *
 * ALGORITHMS EXTRA CREDIT PROGRAMMING ASSN *
 * APRIL 26, 2001                           *
 *                                          *
 * QUICK SORTING ALGORITHM                  *
 *                                          *
 ********************************************/

/************************/
/* FUNCTION PROTOTYPES! */
/************************/

void sort(int *a, int n);
void quickSort(int *array, int l, int r);


/***************************************************/
//This function simply is to comply with
//Dr. Fink's tester.c's call to sort(int *a, int n)
/***************************************************/

void sort(int *a, int n){
	quickSort (a, 0, n-1);
}


/*****************************************/
//This is the actual quick sort function.
/*****************************************/

void quickSort(int *array, int l, int r){

	int i, j, m, iTemp;

	if (l >= r)
		return;
	
	i = l-1;
	j = r;
	m = array[r];
	
	while (i < j){
		do{
			i++;
		}while (array[i] < m);

		do{
			j--;
		}while (array[j] > m);

		if (i < j){
			iTemp = array[i];
			array[i] = array[j];
			array[j]= iTemp;
		}
	}

	iTemp = array[i];
	array[i] = array[r];
	array[r]= iTemp;

	quickSort (array, l, i-1);
	quickSort (array, i+1, r);

	return;
}