/*
 * 	quicksort.c - A general quicksort implementation in C
 * 	author: daniel "bodom_lx" Graziotin <bodom_lx AT task3 DOT cc>
 *  	Quicksort implementation in C
 *	Input: 	array A of integer {10,7,6,8,9,5,3,2,4,3,1,2};
 *	Output: array A of integers such that A[0] <= A[1] <= ... <= A[n]
 */

#include <stdio.h>
#include <stdlib.h>

int A[] = {10,7,6,8,9,5,2,4,3,1};				// change it as you want, remember that qsort works with distinct values
int ARRAY_SIZE = sizeof(A) / sizeof(A[0]);


void swap(int A[], int key1, int key2);				/* swaps two array elements */
int partition( int A[], int left, int right);			/* partition an array such that: lower part <=  higher part. */
void quicksort( int A[], int left, int right);			/* uses partition to sort the array */

void print();							/* auxiliary: to print the array */


void swap(int A[], int key1, int key2){
	int tmp; 
	tmp = A[key2];
	A[key2] = A[key1];
	A[key1] = tmp;	
}

int partition( int A[], int left, int right) {
	int pivot; 
	pivot = A[right];									
	while(1){
		while( A[right] > pivot){			// while the elements starting from right are > than the last element
			right--;				// divide the problem
		}
		while( A[left] < pivot){			// while the elements starting from left are < than the last element
			left++;					// divide the problem (A[] considered becomes smaller)
		}
		if( left < right ){								
			swap(A,left,right);			// swap the elements OR
		}else{
			return left;				// return a new left "pointer" 							
		}
	}
}

void quicksort( int A[], int left, int right){
	int m;
	if( left < right ) {					// make sure that we are trying to sort a subarray
		m = partition( A, left, right);			// divide and conquer
		quicksort( A, left, m-1);			// sort both subarrays
		quicksort( A, m+1, right);
	}	
}


int main() {
	int i;
	printf("\n\nUnsorted array is:  ");
	for(i = 0; i < ARRAY_SIZE; ++i)
		printf(" %d ", A[i]);

	quicksort( A, 0, ARRAY_SIZE - 1);

	printf("\n\nSorted array is:  ");
	for(i = 0; i < ARRAY_SIZE; ++i)
		printf(" %d ", A[i]);
	printf("\n");
}

void print(){
	int i;
	for(i = 0; i < ARRAY_SIZE; ++i)
		printf(" %d ", A[i]);
	printf("\n");
}