This quicksort implements the basic recursive algorithm with three improvements. The first improvement is choosing the pivot based on the median of three values in the list to be sorted. This minimizes the chances of a worst case scenario. The second improvement speeds up the algorithm by termination when subfiles of a certain size are reached. At that point continuing the recursion is not as effective as calling insertion sort on the almost sorted list. The last improvement protects against worst case behavior if there are large numbers of duplicates on the list by partitioning three ways instead of two: all items that are smaller than the pivot, all items that are equal to the pivot, and all items that are greater than the pivot.

One more improvement can be made to bring this implementation to production quality. It must be generalized for any type by accepting pointers to void and a comparison function.

one might also remove tail recursion, but on modern machines this isn't nearly the issue that it once was.

This is great work!!!
``````#include <stdio.h>
#include <stdlib.h>

#define CUTOFF 10
#define length(x) ( sizeof x / sizeof *x )

struct pivots {
int left, right;
};

void swap ( int *a, int *b );
void insertion_sort ( int list[], int left, int right );
int median ( int list[], int left, int right );
struct pivots partition ( int list[], int left, int right );
void quicksort_r ( int list[], int left, int right );
void quicksort ( int list[], int left, int right );

int main ( void )
{
int list[1000];
int i;

for ( i = 0; i < length ( list ); i++ )
list[i] = (int)( (double)rand() / RAND_MAX * 100 );

for ( i = 0; i < length ( list ); i++ )
printf ( "%-4d", list[i] );
printf ( "\n\n" );

quicksort ( list, 0, length ( list ) );

for ( i = 0; i < length ( list ); i++ )
printf ( "%-4d", list[i] );
printf ( "\n" );

return 0;
}

void swap ( int *a, int *b )
{
int save = *a;
*a = *b;
*b = save;
}

void insertion_sort ( int list[], int left, int right )
{
int i, j;

for ( i = left + 1; i < right; i++ ) {
int save = list[i];

for ( j = i; j > 0 && list[j - 1] > save; j-- )
list[j] = list[j - 1];

list[j] = save;
}
}

int median ( int list[], int left, int right )
{
/* Find the median of three values in list, use it as the pivot */
int mid = ( left + right ) / 2;

if ( list[left] > list[mid] )
swap ( &list[left], &list[mid] );

if ( list[left] > list[right] )
swap ( &list[left], &list[right] );

if ( list[mid] > list[right] )
swap ( &list[mid], &list[right] );

swap ( &list[mid], &list[right - 1] );

return list[right - 1];
}

struct pivots partition ( int list[], int left, int right )
{
int k;
int i = left, j = right - 1;
int m = left, n = right - 1;
int pivot = median ( list, left, right );
struct pivots ret;

/* Three way partition <,==,> */
for ( ; ; ) {
while ( list[++i] < pivot )
;
while ( list[--j] > pivot ) {
if ( j == left )
break;
}

if ( i >= j )
break;

swap ( &list[i], &list[j] );

if ( list[i] == pivot )
swap ( &list[++m], &list[i] );

if ( list[j] == pivot )
swap ( &list[--n], &list[j] );
}

swap ( &list[i], &list[right - 1] );

j = i - 1;
i = i + 1;

for ( k = left; k < m; k++, j-- )
swap ( &list[k], &list[j] );

for ( k = right - 1; k > n; k--, i++ )
swap ( &list[k], &list[i] );

ret.left = i;
ret.right = j;

return ret;
}

void quicksort_r ( int list[], int left, int right )
{
/* Terminate on small subfiles */
if ( left + CUTOFF <= right ) {
struct pivots pivot = partition ( list, left, right );

quicksort_r ( list, left, pivot.right );
quicksort_r ( list, pivot.left, right );
}
}

void quicksort ( int list[], int left, int right )
{
quicksort_r ( list, left, right - 1 );

/* Insertion sort on almost sorted list */
insertion_sort ( list, left, right );
}``````
7
Contributors
7
Replies
11
Views
13 Years
Discussion Span
Last Post by Matt Labbé

Thank you for this!

This code as written only ever executes the O(n^2) insertion sort. quicksort() line 138 calls quicksort_r(), and within quicksort_r() line 128 never succeds and in turn line 131-132 never executes -- ie the quick sort algorithm is never run. Then quicksort_r() returns, and quicksort() line 141 always executes, always the insertion sort. Moreover, if the conditional in line 128 is set to always succed w/ say an if(1), then the code in partition() fails and throws a seg fault.

Users beware, this code is broken :(

-SS

I was incorrect, I rescind my above comment.

Is There Any Expert who can help me write "C" program to implements bubble sort using doubly linked list??

I have built a quicksort application but it is nowhere near as efficient & tidy as this ! nice work!

Nice.
Just one question: What is the license of that code?

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.