quick_sort.c

/* Implementaion of quicksort in C*/
#include<stdio.h>

/*swap two elements*/
void swap(int *a,int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

/* print array */
void printArray(int A[], int N)
{
	int i=0;
	for (i = 0; i < N; ++i)
	{
		printf("%d ",A[i]);
	}
}


/* recursivley partition the sub-arrays  */
void quickSort(int A[], int iBegin, int iEnd)
{
	int iPivot; // pivot index
	if (iBegin < iEnd)
	{	
		iPivot = partition(A, iBegin, iEnd);
		quickSort(A, iBegin, iPivot-1);
		quickSort(A, iPivot+1, iEnd);
		/* code */
	}
}


/* 
    Takes last element in the array as pivot and reorder such that 
    smaller values to its left and larger or equal values to its right
	iBegin : Beginn index
	iEnd   : End index
 */
int partition(int A[], int iBegin, int iEnd)
{
	int pivotValue = A[iEnd];
	int storeIndex = iBegin;
	int i;
	for (i = iBegin; i < iEnd; ++i)
	{
		if(A[i] < pivotValue)
		{
			swap(&A[i], &A[storeIndex]);
			storeIndex++;
		}
	}
	swap(&A[iEnd], &A[storeIndex]);
	return storeIndex;
}

int main()
{
	int T,N;
	int A[200];
	int i,j;
	scanf("%d",&T);
	for(i=0; i<T; i++)
	{
		scanf("%d",&N);
		for(j=0; j<N; j++)
		{
			scanf("%d",&A[j]);
		}
		quickSort(A,0,N-1);
		printArray(A,N);
		printf("\n");
	}
	return 0;
}