Quicksort – recursive implementation

May 4th, 2011

For today, recursive implementation of quicksort. The important points to remember: quicksort is O(n lg n) and is not stable. Worst case is O(n*n) – pretty bad. Choice of pivot point is an issue.

void quicksortRecursive(int * a, int l, int h){
int m = (l + h) / 2;
int i = l;
int j = h ;
int p = a[m];
while (i <=j){
while (a[i] < p)
i++;
while (a[j] > p)
j–;
if (i <= j ){
int t = a[i];
a[i]=a[j];
a[j]=t;
i++;
j–;
}
}

if (i < h)
quicksortRecursive(a, i, h);
if (j > l)
quicksortRecursive(a, l, j);

}

Advertisements

~ by Monsi.Terdex on May 4, 2011.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: