Re: what type of sort is this?
- From: "user923005" <dcorbit@xxxxxxxxx>
- Date: 26 Jan 2007 19:14:32 -0800
After a bit of fiddling, I did get some improvement:
/* BEGIN e_driver.c program output */
Timing 6 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 s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.672000 0.734000 0.656000 0.625000 0.687000 0.641000
0x200000 0.657000 0.766000 0.672000 0.657000 0.626000 0.641000
Total times:
s3sort: 1.329000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.500000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.328000 e_type Shellsort, Sedgewick numbers
DCsort: 1.282000 Gonnet Shellsort
Sesort: 1.313000 Sedgewick Shellsort
optisort: 1.282000 optimal increment insertion sort
Distribution #2: Reverse sorted
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.202000 0.218000 0.250000 0.250000 0.266000 0.234000
0x200000 0.203000 0.219000 0.250000 0.250000 0.265000 0.234000
Total times:
s3sort: 0.405000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.437000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.500000 e_type Shellsort, Sedgewick numbers
DCsort: 0.500000 Gonnet Shellsort
Sesort: 0.531000 Sedgewick Shellsort
optisort: 0.468000 optimal increment insertion sort
Distribution #3: Ramp, Drives center pivot qsorts, quadratic
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.203000 0.203000 0.187000 0.265000 0.218000 0.234000
0x200000 0.204000 0.219000 0.188000 0.266000 0.219000 0.251000
Total times:
s3sort: 0.407000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.422000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.375000 e_type Shellsort, Sedgewick numbers
DCsort: 0.531000 Gonnet Shellsort
Sesort: 0.437000 Sedgewick Shellsort
optisort: 0.485000 optimal increment insertion sort
Distribution #4: Two values, Badly written qsorts choke on this
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.172000 0.171000 0.156000 0.296000 0.234000 0.266000
0x200000 0.173000 0.172000 0.156000 0.282000 0.235000 0.251000
Total times:
s3sort: 0.345000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.343000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.312000 e_type Shellsort, Sedgewick numbers
DCsort: 0.578000 Gonnet Shellsort
Sesort: 0.469000 Sedgewick Shellsort
optisort: 0.517000 optimal increment insertion sort
Distribution #5: Already sorted
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.094000 0.078000 0.063000 0.234000 0.140000 0.203000
0x200000 0.094000 0.077000 0.062000 0.234000 0.140000 0.203000
Total times:
s3sort: 0.188000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.155000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.125000 e_type Shellsort, Sedgewick numbers
DCsort: 0.468000 Gonnet Shellsort
Sesort: 0.280000 Sedgewick Shellsort
optisort: 0.406000 optimal increment insertion sort
Distribution #6: Constant
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.094000 0.078000 0.062000 0.219000 0.140000 0.203000
0x200000 0.094000 0.095000 0.064000 0.220000 0.141000 0.204000
Total times:
s3sort: 0.188000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.173000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.126000 e_type Shellsort, Sedgewick numbers
DCsort: 0.439000 Gonnet Shellsort
Sesort: 0.281000 Sedgewick Shellsort
optisort: 0.407000 optimal increment insertion sort
Distribution #7: 32 bit RAND
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.656000 0.750000 0.671000 0.687000 0.625000 0.656000
0x200000 0.704000 0.813000 0.704000 0.642000 0.626000 0.657000
Total times:
s3sort: 1.360000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.563000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.375000 e_type Shellsort, Sedgewick numbers
DCsort: 1.329000 Gonnet Shellsort
Sesort: 1.251000 Sedgewick Shellsort
optisort: 1.313000 optimal increment insertion sort
Distribution #8: Five values
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.249000 0.249000 0.250000 0.328000 0.312000 0.297000
0x200000 0.234000 0.249000 0.250000 0.327000 0.312000 0.297000
Total times:
s3sort: 0.483000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.498000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.500000 e_type Shellsort, Sedgewick numbers
DCsort: 0.655000 Gonnet Shellsort
Sesort: 0.624000 Sedgewick Shellsort
optisort: 0.594000 optimal increment insertion sort
Distribution #9: Ten values
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.265000 0.312000 0.296000 0.344000 0.359000 0.327000
0x200000 0.266000 0.297000 0.296000 0.343000 0.359000 0.328000
Total times:
s3sort: 0.531000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.609000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.592000 e_type Shellsort, Sedgewick numbers
DCsort: 0.687000 Gonnet Shellsort
Sesort: 0.718000 Sedgewick Shellsort
optisort: 0.655000 optimal increment insertion sort
Distribution #10: Twenty values
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.298000 0.376000 0.329000 0.407000 0.392000 0.375000
0x200000 0.297000 0.360000 0.344000 0.376000 0.391000 0.376000
Total times:
s3sort: 0.595000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.736000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.673000 e_type Shellsort, Sedgewick numbers
DCsort: 0.783000 Gonnet Shellsort
Sesort: 0.783000 Sedgewick Shellsort
optisort: 0.751000 optimal increment insertion sort
Distribution #11: 0x7fff values
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.594000 0.689000 0.626000 0.594000 0.610000 0.594000
0x200000 0.579000 0.688000 0.610000 0.579000 0.579000 0.579000
Total times:
s3sort: 1.173000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.377000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.236000 e_type Shellsort, Sedgewick numbers
DCsort: 1.173000 Gonnet Shellsort
Sesort: 1.189000 Sedgewick Shellsort
optisort: 1.173000 optimal increment insertion sort
Distribution #12: Camel, for floating types
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.109000 0.109000 0.094000 0.234000 0.156000 0.203000
0x200000 0.109000 4.281000 0.093000 0.281000 0.172000 0.218000
Total times:
s3sort: 0.218000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.390000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.187000 e_type Shellsort, Sedgewick numbers
DCsort: 0.515000 Gonnet Shellsort
Sesort: 0.328000 Sedgewick Shellsort
optisort: 0.421000 optimal increment insertion sort
Distribution #13: Perverse
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.344000 0.375000 0.344000 0.439000 0.422000 0.391000
0x200000 0.344000 0.360000 0.344000 0.391000 0.376000 0.376000
Total times:
s3sort: 0.688000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.735000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.688000 e_type Shellsort, Sedgewick numbers
DCsort: 0.830000 Gonnet Shellsort
Sesort: 0.798000 Sedgewick Shellsort
optisort: 0.767000 optimal increment insertion sort
Distribution #14: card_shuffle
N s3sort s8sort spsort DCsort Sesort optisort
0x1fffff 0.391000 0.220000 0.157000 0.282000 0.204000 0.250000
0x200000 0.376000 4.376000 0.156000 0.282000 0.204000 0.235000
Total times:
s3sort: 0.767000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.596000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.313000 e_type Shellsort, Sedgewick numbers
DCsort: 0.564000 Gonnet Shellsort
Sesort: 0.408000 Sedgewick Shellsort
optisort: 0.485000 optimal increment insertion sort
/* END e_driver.c program output */
.
- References:
- Re: what type of sort is this?
- From: user923005
- Re: what type of sort is this?
- From: user923005
- Re: what type of sort is this?
- From: user923005
- Re: what type of sort is this?
- Prev by Date: Re: Asymptotic Time Complexity
- Next by Date: invitation
- Previous by thread: Re: what type of sort is this?
- Next by thread: Other than php/perl/lisp/c/c++/java, anybody have a favorite computer-programming language?
- Index(es):
Relevant Pages
|
