home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_11_07
/
qsort.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-02-04
|
3KB
|
76 lines
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define MIN_SIZE 4
#define MEMSWAP( A, B, TEMP, SIZE) { memcpy( (TEMP), (A), (SIZE)); \
memcpy( (A), (B), (SIZE)); memcpy( (B), (TEMP), (SIZE)); }
int my_qsort( char *data, unsigned n_elements, unsigned element_size,
int (*compare)(void *elem1, void *elem2))
{
unsigned start[18], size[18], n_pieces = 1, curr_size;
unsigned size1, size2;
char *startptr, *endptr, *pivot, *tbuff;
int comp;
tbuff = _alloca( element_size);
start[0] = 0;
size[0] = n_elements;
while( n_pieces)
{
pivot = startptr = data + start[n_pieces - 1] * element_size;
curr_size = size[n_pieces - 1];
if( curr_size < MIN_SIZE) /* bubblesort em */
{
unsigned i, j;
char *tptr1, *tptr2;
for( tptr1 = pivot, i = 0; i < curr_size; i++, tptr1 += element_size)
for( tptr2 = tptr1 + element_size, j = i + 1; j < curr_size;
j++, tptr2 += element_size)
if( (compare)(tptr1, tptr2) > 0)
MEMSWAP( tptr1, tptr2, tbuff, element_size);
n_pieces--;
}
else
{
if( curr_size > 10)
MEMSWAP( pivot, pivot + (curr_size / 2) * element_size, tbuff,
element_size);
endptr = startptr + (curr_size - 1) * element_size;
startptr += element_size;
while( startptr <= endptr)
{
comp = (compare)(startptr, pivot);
if( comp > 0)
{
MEMSWAP( endptr, startptr, tbuff, element_size);
endptr -= element_size;
}
else
startptr += element_size;
}
startptr -= element_size;
MEMSWAP( pivot, startptr, tbuff, element_size);
size1 = (startptr - pivot) / element_size;
size2 = curr_size - size1 - 1;
if( size2 < size1)
{
start[n_pieces] = start[n_pieces - 1] + size1 + 1;
size[n_pieces] = size2;
size[n_pieces - 1] = size1;
}
else
{
start[n_pieces] = start[n_pieces - 1];
start[n_pieces - 1] += size1 + 1;
size[n_pieces - 1] = size2;
size[n_pieces] = size1;
}
n_pieces++;
}
}
return( 0);
}