• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2215
  • Last Modified:

Most efficient gap sequence for the shell sort

Hi there, I've been experimenting with the shell sort and I seem to get the quickest sort times when I start the gap sequence at half the size of the sequence, and then divide it by 2.2 for each pass until its done. The thing is, I cannot find an explanation for why 2.2 seems to be the quickest. Does anyone have any insight on this?
0
terminal434
Asked:
terminal434
  • 2
2 Solutions
 
tygrus2Commented:
Have you tried differently ordered/random starting lists ? Describe the lists to be sorted: number of elements, mostly random or partially sequential with a tail ?

I had fun at school with a modified bubble sort that alternated running left and right (like Nightrider' car, KIT lights) and shrank the sort window  for already sorted slots (upper and lower bounds became closer together). I looked it up today and found something similar is can now be called the Cocktail sort. It's good with partially sorted lists but the worse case is no more than half n squared. Your shell sort should theoritically perform better.
0
 
Jose ParrotGraphics ExpertCommented:
Interesting your research and observations.
The subject is far to be closed in a definitive conclusion. By now, thanks to Marcin Ciura, the best gap sequence for Shell sort is
       1, 4, 10, 23, 57, 132, 301, 701, 1750
which is something similar to a geometric progression growth ("similar" because the factor isn't constant, varying around 2.2 and 2.5), as in Fig. 1.

Others sequences were found, like the series
       1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049, 1073643521, 2415771649

Some one has suggested the Fibonacci numbers (this Italian is always around!) but the one from Ciura is assumed as the best until now.

Your number 2.2 can be a particular case, I'm not sure about, but seems to be.
You may want read the cited author, besides Robert Sedgewick and, of course, Donald Shell.
Sedgewick paper at http://www.cs.princeton.edu/~rs/shell/paperF.pdfhttp://www.cs.princeton.edu/~rs/shell/paperF.pdf
is probably a good reference for you.

Jose Shell sort best known sequence
0
 
Jose ParrotGraphics ExpertCommented:
Althought your 2.2 factor seems an empyric number, it is easy to notice that how close to Ciura factors is! The best exlanation on that are, as far we know, in the cited papers. Not a single answer, but long articles.
Jose
0
 
phoffricCommented:
JoseParrot,
Could you please upload the pdf file here. When I use your link, the result is
Sorry, the page you requested couldn't be found.
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now