/*
* Copyright (C) 1989, Mark R. Nelson
*
* This routines sorts an integer array, data[], that has
* size elements. It is used as a boilerplate function
* for a Quicksort, and is intended to replace the ANSI
* qsort() routine.
*
*/
#define SMALLEST_PARTITION 15
my_qsort( int *data, int size )
{
register int i;
register int j;
int first;
int last;
int temp;
int stack_pointer;
struct {
int left;
int right;
} stack[100];
/*
* The stack structure is used to hold a list of left and
* right pairs. These pairs define partitions that still
* need to be sorted. When the stack pointer drops below
* zero, it means all the quicksort partitions have been
* done.
*/
stack_pointer = 0;
stack[0].left = 0;
stack[0].right = size-1;
/*
* The while loop below here is the Quicksort partitioning
* code. It runs until there are no more (left,right)
* pairs left on the stack. When it is complete, the
* insertion sort over the whole array still needs to be
* done.
*/
while (stack_pointer>=0)
{
first = stack[stack_pointer].left;
last = stack[stack_pointer].right;
stack_pointer--;
/*
* Here is where I swap the first and middle records, in
* hopes of finding a good key.
*/
temp = data[ first ];
data[first] = data[ (last+first)/2 ];
data[ (last+first)/2 ] = temp;
/*
* The while loop here is the main loop of the Quicksort.
* It moves i up and j down until j is positioned at
* the correct spot where data[0] belongs. There may
* or my not be some exchanges along the way.
*/
i = first+1;
j = last;
while ( i <= j )
{
while ( data[i] <= data[first] && i <= last )
i++;
while ( data[j] >= data[first] && j > first )
j--;
if( j > i )
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
/*
* At this point, j is pointing to the final position in
* the array for data[first]. After an exchange, data[j]
* is set, and will not have to be moved again, ever.
*/
temp = data[first];
data[first] = data[j];
data[j] = temp;
/*
* After the partitioning is complete, there are two
* smaller partitions that may need to have a Quicksort
* performed on them. This is done here. A good
* programmer would probably check for stack overflow here.
*/
if ( (j-first) >= SMALLEST_PARTITION )
{
stack[++stack_pointer].left = first;
stack[stack_pointer].right = j-1;
}
if ( (last-j) >= SMALLEST_PARTITION )
{
stack[++stack_pointer].left = j+1;
stack[stack_pointer].right = last;
}
}
/*
* When we reach this point, the Quicksort portion of the
* routine is complete, and it is time for the insertion sort.
*/
for ( i=1 ; i<size ; i++ )
{
temp = data[i];
j = i-1;
while ( j >= 0 )
{
if ( data[j] > temp )
{
data[j+1] = data[j];
j--;
}
else
break;
}
data[j+1] = temp;
}
}