Solved

Most efficient gap sequence for the shell sort

Posted on 2011-03-10
4
1,805 Views
Last Modified: 2012-05-11
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
Comment
Question by:terminal434
  • 2
4 Comments
 
LVL 5

Expert Comment

by:tygrus2
ID: 35107228
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
 
LVL 18

Accepted Solution

by:
JoseParrot earned 500 total points
ID: 35108530
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
 
LVL 18

Assisted Solution

by:JoseParrot
JoseParrot earned 500 total points
ID: 35134412
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
 
LVL 32

Expert Comment

by:phoffric
ID: 35134845
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.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Storing historical updates in a database 9 128
Two list de-cypher 6 101
Help with Javascript syntax 4 110
Best prediction based on two lists of numbers  in excel 2 60
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Email security requires an ever evolving service that stays up to date with counter-evolving threats. The Email Laundry perform Research and Development to ensure their email security service evolves faster than cyber criminals. We apply our Threat…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

830 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question