Category : C Source Code
Archive   : BFSORTS.ZIP
Filename : SSORT.C

/***********************************************************************/
/* SORT(): Non-Recursive Shell's Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/
/* Shell's sort. Not bad for intermediate sizes. */
/* Uses increment sequence h(n+1) = 3*h(n) + 1, */
/* as suggested by Knuth. */

#include
#include
#include
#include

#include "sort.h"

#define VERBOSE (0)

static char *base;
static double *dbase;
static int nelem, width;
static int (*compare) (void *, void *);
static int get_increment (int n_elements);
static char *temp_record;

int
ssort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
register unsigned int increment;
long offset;
register unsigned int equiv_class;

base = pbase;
dbase = pbase; /* for debugging only */
nelem = pnelem;
width = pwidth;
compare = pcompare;

temp_record = malloc (width);
if (temp_record == NULL)
return S_NOMEM;

for (increment = get_increment (nelem);
increment > 0;
increment /= 3)
{
for (equiv_class = increment;
equiv_class < nelem;
equiv_class++)
{
memcpy (temp_record, base + equiv_class * width, width);
for (offset = equiv_class - increment;
offset >= 0 &&
#pragma warn -sig
(*compare) (temp_record, base + offset * width) < 0;
#pragma warn .sig
offset -= increment)
{
#pragma warn -sig
memcpy (base + (increment + offset) * width,
base + offset * width,
#pragma warn .sig
width);
} /* end for offset */

#pragma warn -sig
memcpy (base + (offset + increment) * width, temp_record, width);
#pragma warn .sig
} /* end for equiv_class */
} /* end for increment */

return S_OK;
} /* end ssort */

int
get_increment (int n_elements)
{
register int inc;

for (inc = 1;
inc < n_elements;
inc = 3 * inc + 1)
;

return inc > 17 ? inc/9 : 1;
} /* end get_increment */