C and C++ Programming Resources

Custom Search

Quicksort in C Programming Language

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).

Quick Sort Demo

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".

There are No Comments to this post. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response or TrackBack from your own site.


Leave a Reply

You must be logged in to post a comment.