Re: what type of sort is this?

On Jan 26, 2:02 pm, pete <pfil...@xxxxxxxxxxxxxx> wrote:
user923005 wrote:
For certain sets, shellsort works marvelously (typically between set
sizes of 100 and 100K items), provided that the data is not reverse
sorted or approximately reverse sorted (which is the worst case input
for insertion sort and the closely related shellsort).My observation from timed tests and also from comparison tallying,
is that random order is a much worse case than reversed order,
for Shellsort.

The performance of the N /= 2 increment scheme,
is worst for disordered arrays of (1 << X) number of elements.

Timed tests were done using the e_driver program,
which is in 6 files at:http://www.mindspring.com/~pfilandr/C/e_driver/

Comparison tallies were done using q_sort.c at:http://www.mindspring.com/~pfilandr/C/q_sort/q_sort.c

/* BEGIN e_driver.c program output */

Timing 4 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N s2sort s3sort s8sort spsort
0x1fffff 3.234000 2.390000 2.359000 2.187000
0x200000 10.734000 2.375000 2.344000 2.172000
Total times:
s2sort: 13.968000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 4.765000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.703000 e_type Shellsort, 3 / 8 increment ratio
spsort: 4.359000 e_type Shellsort, Sedgewick numbers

Distribution #2: Reverse sorted
N s2sort s3sort s8sort spsort
0x1fffff 1.516000 1.141000 1.062000 1.000000
0x200000 1.610000 1.157000 1.094000 1.016000
Total times:
s2sort: 3.126000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 2.298000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 2.156000 e_type Shellsort, 3 / 8 increment ratio
spsort: 2.016000 e_type Shellsort, Sedgewick numbers

/* END e_driver.c program output */

Followup To: comp.programming

I was very surprised by this finding.

/* BEGIN e_driver.c program output */

Timing 6 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N s2sort s3sort s8sort spsort DCsort Sesort
0x1fffff 1.360000 0.657000 0.704000 0.641000 0.642000 0.594000
0x200000 4.843000 0.656000 0.734000 0.640000 0.625000 0.609000
Total times:
s2sort: 6.203000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 1.313000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.438000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.281000 e_type Shellsort, Sedgewick numbers
DCsort: 1.267000 Gonnet Shellsort
Sesort: 1.203000 Sedgewick Shellsort

Distribution #2: Reverse sorted
N s2sort s3sort s8sort spsort DCsort Sesort
0x1fffff 0.329000 0.204000 0.204000 0.235000 0.251000 0.235000
0x200000 0.343000 0.203000 0.219000 0.219000 0.250000 0.234000
Total times:
s2sort: 0.672000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 0.407000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.423000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.454000 e_type Shellsort, Sedgewick numbers
DCsort: 0.501000 Gonnet Shellsort
Sesort: 0.469000 Sedgewick Shellsort

/* END e_driver.c program output */

.