Compilable header file:

/*

// This is a C++ template for shellsort.

// It can also be called form C, if e_type has a typedef.

// Modification of code by Pete Pfilander by Dann Corbit.

// Use it however you like.

// Send comments and curses to:

dc*****@connx.com
*/

#ifdef __cplusplus

#include <cstdlib/* for definition of size_t */

template <class e_type>

#else

#include <stdlib.h/* for definition of size_t */

#endif

void dcss(e_type * array, size_t h)

{

e_type *i,

*j,

*k,

*after,

temp;

static const float shell_ratio = 0.31023;

size_t inversion = 3;

size_t danger_danger = 0;

after = array + h;

h *= shell_ratio;

while (h != 0) {

i = array + h;

do {

j = i - h;

if (*j *i) {

k = i;

temp = *k;

do {

*k = *j;

k = j;

if (h + array j) {

break;

}

j -= h;

} while (*j temp);

*k = temp;

}

++i;

} while (i != after);

h *= shell_ratio;

h += danger_danger;

danger_danger = (h <= inversion && h 1);

}

}

Compilable test driver:

#ifdef __cplusplus

#include <cstdio>

#else

#include <stdio.h/* for definition of size_t */

#endif

#include "shellsort.h"

int testvector[1000000];

int main(void)

{

size_t vdim = sizeof testvector / sizeof testvector[0];

size_t index;

for (index = 0; index < vdim; index++) {

testvector[index] = rand();

}

dcss(testvector, vdim);

size_t i;

for (i = 0; i < vdim - 1; i++) {

if (testvector[i] testvector[i + 1]) {

printf("testvector is out of sort at %u (%d,%d)\n",

(unsigned) i, testvector[i], testvector[i + 1]);

}

}

return 0;

}

Output of Pete's program on my machine:

/* BEGIN e_driver.c program output */

Timing 9 different sorting functions.

Sorting arrays of N number of elements,

in 14 different distributions.

The elements are of type long unsigned.

sizeof (long unsigned) is 4.

The times shown are in seconds.

Distribution #1: Shuffled

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.704000 0.735000 0.641000 0.672000 0.767000 0.673000

0.641000 0.642000 0.657000

0x200000 0.687000 0.749000 0.641000 0.671000 0.749000 0.671000

0.641000 0.624000 0.656000

Total times:

dcss: 1.391000 0.31023 float ratio Shellsort (a)

DCsort2c: 1.484000 0.31023 float ratio Shellsort (c)

DCsort2b: 1.282000 0.31023 float ratio Shellsort (b)

s3sort: 1.343000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 1.516000 e_type Shellsort, 3 / 8 increment ratio

spsort: 1.344000 e_type Shellsort, Sedgewick numbers

DCsort: 1.282000 Gonnet Shellsort

Sesort: 1.266000 Sedgewick Shellsort

optisort: 1.313000 Marcin Ciura increment shellsort

Distribution #2: Reverse sorted

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.187000 0.265000 0.188000 0.203000 0.218000 0.250000

0.250000 0.265000 0.249000

0x200000 0.188000 0.251000 0.189000 0.219000 0.219000 0.235000

0.266000 0.266000 0.235000

Total times:

dcss: 0.375000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.516000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.377000 0.31023 float ratio Shellsort (b)

s3sort: 0.422000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.437000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.485000 e_type Shellsort, Sedgewick numbers

DCsort: 0.516000 Gonnet Shellsort

Sesort: 0.531000 Sedgewick Shellsort

optisort: 0.484000 Marcin Ciura increment shellsort

Distribution #3: Ramp, Drives center pivot qsorts, quadratic

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.172000 0.220000 0.188000 0.204000 0.204000 0.204000

0.266000 0.220000 0.250000

0x200000 0.172000 0.204000 0.204000 0.203000 0.203000 0.188000

0.266000 0.235000 0.235000

Total times:

dcss: 0.344000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.424000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.392000 0.31023 float ratio Shellsort (b)

s3sort: 0.407000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.407000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.392000 e_type Shellsort, Sedgewick numbers

DCsort: 0.532000 Gonnet Shellsort

Sesort: 0.455000 Sedgewick Shellsort

optisort: 0.485000 Marcin Ciura increment shellsort

Distribution #4: Two values, Badly written qsorts choke on this

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.156000 0.172000 0.234000 0.172000 0.172000 0.156000

0.297000 0.234000 0.266000

0x200000 0.157000 0.219000 0.220000 0.172000 0.172000 0.157000

0.297000 0.235000 0.281000

Total times:

dcss: 0.313000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.391000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.454000 0.31023 float ratio Shellsort (b)

s3sort: 0.344000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.344000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.313000 e_type Shellsort, Sedgewick numbers

DCsort: 0.594000 Gonnet Shellsort

Sesort: 0.469000 Sedgewick Shellsort

optisort: 0.547000 Marcin Ciura increment shellsort

Distribution #5: Already sorted

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.063000 0.063000 0.157000 0.110000 0.110000 0.063000

0.235000 0.157000 0.219000

0x200000 0.063000 0.063000 0.157000 0.095000 0.079000 0.063000

0.235000 0.157000 0.220000

Total times:

dcss: 0.126000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.126000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.314000 0.31023 float ratio Shellsort (b)

s3sort: 0.205000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.189000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.126000 e_type Shellsort, Sedgewick numbers

DCsort: 0.470000 Gonnet Shellsort

Sesort: 0.314000 Sedgewick Shellsort

optisort: 0.439000 Marcin Ciura increment shellsort

Distribution #6: Constant

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.063000 0.063000 0.157000 0.094000 0.095000 0.063000

0.235000 0.157000 0.220000

0x200000 0.079000 0.063000 0.157000 0.094000 0.079000 0.064000

0.235000 0.157000 0.220000

Total times:

dcss: 0.142000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.126000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.314000 0.31023 float ratio Shellsort (b)

s3sort: 0.188000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.174000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.127000 e_type Shellsort, Sedgewick numbers

DCsort: 0.470000 Gonnet Shellsort

Sesort: 0.314000 Sedgewick Shellsort

optisort: 0.440000 Marcin Ciura increment shellsort

Distribution #7: 32 bit RAND

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.704000 0.750000 0.626000 0.673000 0.751000 0.672000

0.641000 0.626000 0.641000

0x200000 0.703000 0.734000 0.624000 0.671000 0.766000 0.671000

0.640000 0.624000 0.656000

Total times:

dcss: 1.407000 0.31023 float ratio Shellsort (a)

DCsort2c: 1.484000 0.31023 float ratio Shellsort (c)

DCsort2b: 1.250000 0.31023 float ratio Shellsort (b)

s3sort: 1.344000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 1.517000 e_type Shellsort, 3 / 8 increment ratio

spsort: 1.343000 e_type Shellsort, Sedgewick numbers

DCsort: 1.281000 Gonnet Shellsort

Sesort: 1.250000 Sedgewick Shellsort

optisort: 1.297000 Marcin Ciura increment shellsort

Distribution #8: Five values

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.234000 0.265000 0.281000 0.234000 0.265000 0.249000

0.343000 0.327000 0.312000

0x200000 0.235000 0.267000 0.282000 0.235000 0.266000 0.251000

0.329000 0.329000 0.314000

Total times:

dcss: 0.469000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.532000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.563000 0.31023 float ratio Shellsort (b)

s3sort: 0.469000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.531000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.500000 e_type Shellsort, Sedgewick numbers

DCsort: 0.672000 Gonnet Shellsort

Sesort: 0.656000 Sedgewick Shellsort

optisort: 0.626000 Marcin Ciura increment shellsort

Distribution #9: Ten values

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.282000 0.329000 0.329000 0.267000 0.329000 0.298000

0.360000 0.360000 0.329000

0x200000 0.281000 0.312000 0.327000 0.281000 0.313000 0.281000

0.375000 0.422000 0.359000

Total times:

dcss: 0.563000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.641000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.656000 0.31023 float ratio Shellsort (b)

s3sort: 0.548000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.642000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.579000 e_type Shellsort, Sedgewick numbers

DCsort: 0.735000 Gonnet Shellsort

Sesort: 0.782000 Sedgewick Shellsort

optisort: 0.688000 Marcin Ciura increment shellsort

Distribution #10: Twenty values

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.313000 0.376000 0.360000 0.297000 0.407000 0.329000

0.392000 0.407000 0.391000

0x200000 0.313000 0.360000 0.360000 0.297000 0.360000 0.344000

0.376000 0.391000 0.391000

Total times:

dcss: 0.626000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.736000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.720000 0.31023 float ratio Shellsort (b)

s3sort: 0.594000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.767000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.673000 e_type Shellsort, Sedgewick numbers

DCsort: 0.768000 Gonnet Shellsort

Sesort: 0.798000 Sedgewick Shellsort

optisort: 0.782000 Marcin Ciura increment shellsort

Distribution #11: 0x7fff values

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.641000 0.689000 0.563000 0.610000 0.688000 0.626000

0.610000 0.610000 0.610000

0x200000 0.656000 0.703000 0.578000 0.609000 0.687000 0.641000

0.593000 0.609000 0.594000

Total times:

dcss: 1.297000 0.31023 float ratio Shellsort (a)

DCsort2c: 1.392000 0.31023 float ratio Shellsort (c)

DCsort2b: 1.141000 0.31023 float ratio Shellsort (b)

s3sort: 1.219000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 1.375000 e_type Shellsort, 3 / 8 increment ratio

spsort: 1.267000 e_type Shellsort, Sedgewick numbers

DCsort: 1.203000 Gonnet Shellsort

Sesort: 1.219000 Sedgewick Shellsort

optisort: 1.204000 Marcin Ciura increment shellsort

Distribution #12: Camel, for floating types

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.094000 0.125000 0.156000 0.110000 0.094000 0.110000

0.251000 0.173000 0.219000

0x200000 0.079000 0.094000 0.157000 0.110000 4.360000 0.095000

0.251000 0.172000 0.219000

Total times:

dcss: 0.173000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.219000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.313000 0.31023 float ratio Shellsort (b)

s3sort: 0.220000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 4.454000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.205000 e_type Shellsort, Sedgewick numbers

DCsort: 0.502000 Gonnet Shellsort

Sesort: 0.345000 Sedgewick Shellsort

optisort: 0.438000 Marcin Ciura increment shellsort

Distribution #13: Perverse

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.344000 0.360000 0.360000 0.329000 0.376000 0.344000

0.391000 0.376000 0.391000

0x200000 0.343000 0.359000 0.359000 0.359000 0.374000 0.359000

0.406000 0.390000 0.406000

Total times:

dcss: 0.687000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.719000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.719000 0.31023 float ratio Shellsort (b)

s3sort: 0.688000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 0.750000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.703000 e_type Shellsort, Sedgewick numbers

DCsort: 0.797000 Gonnet Shellsort

Sesort: 0.766000 Sedgewick Shellsort

optisort: 0.797000 Marcin Ciura increment shellsort

Distribution #14: card_shuffle

N dcss DCsort2c DCsort2b s3sort s8sort

spsort DCsort Sesort optisort

0x1fffff 0.204000 0.250000 0.188000 0.391000 0.235000 0.204000

0.297000 0.204000 0.266000

0x200000 0.204000 0.282000 0.188000 0.407000 4.469000 0.172000

0.282000 0.204000 0.251000

Total times:

dcss: 0.408000 0.31023 float ratio Shellsort (a)

DCsort2c: 0.532000 0.31023 float ratio Shellsort (c)

DCsort2b: 0.376000 0.31023 float ratio Shellsort (b)

s3sort: 0.798000 e_type Shellsort, 3 / 7 increment ratio

s8sort: 4.704000 e_type Shellsort, 3 / 8 increment ratio

spsort: 0.376000 e_type Shellsort, Sedgewick numbers

DCsort: 0.579000 Gonnet Shellsort

Sesort: 0.408000 Sedgewick Shellsort

optisort: 0.517000 Marcin Ciura increment shellsort

accumulator sums = 8.321000, 9.322000, 8.871000

/* END e_driver.c program output */