Sort the elements of an array A in ascending order.

Quick-sort uses recursive calls for sorting the elements.

Is an example for divide-and-conquer algorithmic technique.
Divide: the array A[low … high] is partitioned into two non-empty sub arrays

1. A[low … q] and A[q+1 … high],
2. such that each element of A[low … q] is less than or equal to each element of A[q+1 … high].
3. The index q is computed as part of this portioning procedure.

Conquer: The two sub arrays A[low … q] and A[q+1 … high] are sorted by recursive calls to Quick sort.

The recursive algorithm consists of four steps:

1. If there is one or no elements in the array to be sorted, return.
2. Pick an element in the array to serve as “pivot” point. (usually the leftmost element in the array is used).
3. Split the array into two parts – one with elements larger than the pivot and the other with elements smaller than the pivot.
4. Recursively repeat the algorithm for both halves of the original array.

#include<stdio.h>
#include<conio.h>
#define SIZE 50

void swap(int *A, int i, int j)
{
    int aux;
    aux=A[i];
    A[i]=A[j];
    A[j]=aux;
}

int Partition(int A[], int low, int high)
{
	int left, right, pivot_item=A[low];
	left = low+1; right = high;

	while(left<=right)
	{
		/* Move left while item < pivot */
		while(A[left] <= pivot_item && left<=right) 	left ++;
		/* Move right while item > pivot */
		while(A[right] > pivot_item && left<=right) 	right --;
		if(left<right) { swap(A, left, right); left ++; right --; }
	}
	/* right is final position for the pivot */
	A[low]=A[right];
	A[right]=pivot_item;
	return right;
}

void QuickSort(int A[], int low, int high)
{
	int pivot ;
	/* Terminal Condition */ 
	if(high > low)
	{
		pivot = Partition(A, low, high);
		QuickSort(A, low, pivot-1);
		QuickSort(A, pivot+1, high);
	}
}

void sort(int A[], int N)
{
	QuickSort(A, 0, N-1);
}




void main()
{
	int A[SIZE], N;
	int i;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);

	for (i = 0; i < N; i++)
	{
		printf("Enter A[%d]: ", i);
		scanf("%d", &A[i]);
	}

 	sort(A,N);

	printf("\n\n** After sorting ** \n");
	for (i = 0; i < N; i++)
	{
		printf("A[%d]=%d\n", i, A[i]);
	}

	getch();
}