Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Most efficient gap sequence for the shell sort

Posted on 2011-03-10
Medium Priority
2,070 Views
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
Question by:terminal434
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 2

LVL 5

Expert Comment

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

Jose Parrot earned 2000 total points
ID: 35108530
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
0

LVL 18

Assisted Solution

Jose Parrot earned 2000 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

ID: 35134845
JoseParrot,
Sorry, the page you requested couldn't be found.
0

## Featured Post

Question has a verified solution.

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

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…
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
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…
In this video, Percona Solutions Engineer Barrett Chambers discusses some of the basic syntax differences between MySQL and MongoDB. To learn more check out our webinar on MongoDB administration for MySQL DBA: https://www.percona.com/resources/we…
###### Suggested Courses
Course of the Month8 days, 20 hours left to enroll