Code:
#include<stdio.h>
#define N 100 /* size of array, and four macros below */
#define swap(x, y) { int t; t = x; x = y; y = t;}
#define order(x, y) if (x > y) swap(x, y)
#define o2(x, y) order(x, y)
#define o3(x, y, z) o2(x, y); o2(x, z); o2(y, z)
typedef enum
{
yes, no
} yes_no; /*enumeration type yes_no */
/* pivot is attempted to be different than the smallest value of 3 args */
static yes_no find_pivot(int *left, int *right, int *pivot_ptr)
{
int a, b, c, *p;
a = *left; /* left value */
b = *(left + (right - left) / 2); /* middle value */
c = *right; /* right value */
o3(a, b, c); /* order a, b, c */
if ( a < b )
{ /* pivot will be b */
*pivot_ptr = b;
return yes;
}
if ( b < c )
{ /* a == b, pivot will be c */
*pivot_ptr = c;
return yes;
}
for ( p = left +1; p <= right; ++p )
{ /* trying to find another pivot != left */
if ( *p != * left )
{
*pivot_ptr = (*p < *left) ? *left : *p;
return yes;
}
}
return no; /* all elements of an array have the same value */
}
static int *partition(int *left, int *right, int pivot)
{
while ( left <= right )
{
while ( *left < pivot )
{
++left; /* no action */
}
while ( *right >= pivot )
{
--right;
}
if ( left < right )
{ /* exchanging value to keep < ordering */
swap(*left, *right);
++left;
--right;
}
}
return left;
}
int count = 0;
void quicksort(int *left, int *right) /* recursive algorithm */
{
int *p, pivot;
++count;
if ( find_pivot(left, right, &pivot) == yes )
{
p = partition(left, right, pivot);
/* moving all elements < pivot to left partition, */
/* and >= 0 to right partition */
quicksort(left, p - 1);
quicksort(p, right);
}
}
int main(void)
{
int i;
int a[N] =
{
33, 82, 91, 36, 24, 22, 54, 81, 44, 24, 33, 28, 71, 69, 57, 90,
99, 9, 14, 56, 8, 72, 63, 13, 37, 48, 8, 8, 60, 41, 91, 64,
12, 46, 23, 14, 58, 89, 70, 63, 27, 74, 46, 3, 24, 76, 2, 28,
63, 28, 65, 78, 45, 78, 71, 31, 4, 9, 7, 38, 47, 98, 88, 17,
91, 23, 19, 11, 60, 85, 93, 47, 36, 28, 29, 58, 87, 74, 24, 14,
35, 98, 20, 12, 62, 65, 78, 75, 46, 46, 48, 94, 72, 18, 78, 59,
87, 59, 8, 16,
};
quicksort(a, a + N -1);
for ( i = 0; i < N; i++ )
{
printf("%2d,%c", a[i], i % 16 == 15 ? '\n' : ' ');
}
putchar('\n');
printf("count = %d\n", count);
return 0;
}
/* my output
2, 3, 4, 7, 8, 8, 8, 8, 9, 9, 11, 12, 12, 13, 14, 14,
14, 16, 17, 18, 19, 20, 22, 23, 23, 24, 24, 24, 24, 27, 28, 28,
28, 28, 29, 31, 33, 33, 35, 36, 36, 37, 38, 41, 44, 45, 46, 46,
46, 46, 47, 47, 48, 48, 54, 56, 57, 58, 58, 59, 59, 60, 60, 62,
63, 63, 63, 64, 65, 65, 69, 70, 71, 71, 72, 72, 74, 74, 75, 76,
78, 78, 78, 78, 81, 82, 85, 87, 87, 88, 89, 90, 91, 91, 91, 93,
94, 98, 98, 99,
count = 125
*/
[edit]