Quicksort is a well-known sorting algorithm developed by C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962). Quicksort is said to be the fastest sorting algorithm in practice. On average it makes Θ(nlogn) (big O notation) comparisons to sort n items, but in the worst cases it isas slow as bubble sort. Visually you can see below that how quicksort works (divide and conquer strategy).

Here I am going to demonstrate a simple Quicksort demo. I have run and tested this on Dev C++ version 4.9.

#include<conio.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
int x[] = {1,3,2,4,6,8,7,9,5};
void Swap(int i, int j){
int temp;
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
int random(int min, int max)
{
return (int)((max - min) * rand()/(float)RAND_MAX + min);
}
void QuickSort(int iLowerBound, int iUpperBound){
int i, m;
if(iLowerBound >= iUpperBound)
return;
Swap(iLowerBound, random(iLowerBound, iUpperBound));
m = iLowerBound;
for(i=iLowerBound+1; i<=iUpperBound; i++)
if(x[i] < x[iLowerBound])
Swap(++m, i);
Swap(iLowerBound, m);
QuickSort(iLowerBound, m-1);
QuickSort(m+1, iUpperBound);
}
int main (void){
for(int i=0;i<8;i++)
printf("|%d", x[i] );
printf("\n");
QuickSort(0,4);
for(int i=0;i<8;i++)
printf("|%d", x[i] );
getch();
return 0;
}

The video below (Jon Bently) describes three different implementations of Hoare's classic Quicksort algorithm.You can find this implementation and discussion on quicksort in (Andy Oram and Greg Wilson's) book Beautiful Code: Leading Programmers Explain How They Think. under chapter three "The most beautiful code I never wrote".