Most of the quicksort implementations are prettymuch confusing for beginners. When I learned this one, it was really annoying. So I decided to write a simple and self explaining quick sort program. Here we go,
/* Quicksort
*
* Refer book "Introduction to Algorithm" by Thomas H. Cormen, pp: 145
* for Quicksort algorithm.
*
* http://books.google.com/books?id=NLngYyWFl_YC&pg=PA145
*
*
* http://books.google.com/books?id=NLngYyWFl_YC&pg=PA145
*
* Programmer: R. Surendhar ( suren.r@live.in )
* Date: 28.12.2009
* Compiler: GCC
* Parameters: gcc -std=C99 QuickSort.c
*
* WARNING: Compile in C99 compiler.
* If you have old compiler, simply declare the variables immediately
* after the open curl braces '{' in functions.
* Example:
* for(int i=0; i<8;> //C99 mode
* --------------------------------------------------------------
* int i;
* for(i=0; i<8;> //C90 and Older mode
*/
#include
void QuickSort(int[], int, int);
int Partition(int[], int, int);
void Swap(int[], int, int);
int main()
{
int A[] = { 6, 3, 8, 4, 2, 9, 1, 7 };
QuickSort(A, 0, 7);
printf("\n\n");
for (int i = 0; i <>
printf(" %3d", A[i]);
return 0;
}
/**
* QuickSort(A, p, r)
*
* Sorts the part of the Array 'A' defined by starting position 'p',
* ending position 'r'.
**/
void QuickSort(int A[], int p, int r)
{
if (p <>
{
int q = Partition(A, p, r);
QuickSort(A, p, q-1);
QuickSort(A, q+1, r);
}
}
/**
* Partition(A, p, r)
*
* Rearranges the elements in part of the array 'A' defined by the
* starting position 'p' and ending position 'r' in the following
* manner.
* The function selects a pivot element 'x' and the lower half of the
* array A[p..r] contains elements lesser than pivot 'x' and upper half
* contains elements greater than pivot.
* Returns the position of pivot to the calling function after
* rearraging the array.
**/
int Partition(int A[], int p, int r)
{
int i = p - 1;
for (int j = p, x = A[r]; j <= r ; j++)
if(A[j] <= x)
Swap(A, ++i, j);
return i;
}
/**
* Swap(A, i, j)
*
* Interchanges the value stored in the positions 'i' and 'j' in the
* array 'A'.
**/
void Swap(int A[], int i, int j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
