Quick Sort

#include<stdio.h>
#define MAX 10
void qsort(int A[], int p, int r);
int partition(int A[], int p, int r);

main()
{
int Arr[MAX]={10,4,5,6,2,3,8,1,9,7};
int i;
qsort(Arr,0,MAX);

for(i=0;i<MAX;i++)
printf("%d ",Arr[i]);
}

void qsort(int A[], int p, int r)
{
int q;
if(p<r)
{
q=partition(A,p,r);
qsort(A,p,q-1);
qsort(A,q+1,r);
}
}

int partition(int A[], int p, int r)
{
int i , j , x,tmp;
x=A[r];
j=p;
i=p-1;
while(j<r)
{
if(A[j]<x)
{
i=i+1;
// Exchange A[i] & A[j]
tmp=A[j];
A[j]=A[i];
A[i]=tmp;
}
j++;
}
// Exchange A[i+1] & A[r]
tmp=A[i+1];
A[i+1]=A[r];
A[r]=tmp;

return i+1;
}

Output:
1 2 3 4 5 6 7 8 9 10

Time Complexity:
Best - O( n log n )
Average - O(n log n )
Worst - O( n^2)