Talk:Shell sort

From Wikipedia, the free encyclopedia

Contents

[edit] Copyright violation?

This sounds like it might have been taken straight from a copyrighted textbook. Anyone know the source for sure? Wesley

I found a german version which seems to be a word by word translation. Even the examples are the same. Since the german version is longer, it seems that the english text in wikipedia is taken from there. The URL is http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm

80.145.80.78 20:36, 29 Nov 2003 (UTC) (de:Benutzer:Hubi)

Yes, it seems that page has an English version whence much of this article was copied. But it's gone so long without detection that we've made significant changes. I don't know how we can possibly separate the violating from the nonviolating material at this juncture. We may just have to rewrite the article. Deco 18:10, 15 December 2005 (UTC)

Is shell sort different from comb sort?

They are similar but different. Comb sort is to bubbls sort what shell sort is to insertion sort. Bubba73 16:16, August 31, 2005 (UTC)

According to NIST, the difference is that comb sort applies only one pass through the elements at each iteration whereas shell sort completely sorts at each iteration.

Has anyone actually *used* shell sort at all recently? Quicksort is much faster in practice, and just as simple to implement, merge sort give you guaranteed n log n performance and only requires sequential access, heapsort is also guaranteed n log n, in-place, with pretty much no overhead whatsoever, and there are a variety of specialised sorting algorithms - for instance, for strings, which have much lower constant factors. Anybody? --Robert Merkel 14:14 May 14, 2003 (UTC)

I actually use Shell sort regularly. Quicksort isn't that much faster than a good shell sort until you get into millions of items. Bubba73 16:16, August 31, 2005 (UTC)


Shell sort is a very powerful algorithm, especially when used in combination with Insertion sort.

---

I have been testing out Shell sort for the past few weeks and I have found it to be much faster than Heapsort and Mergesort for array inputs of size 5,000,000 and below. Much faster in terms of time as well as the number of swaps and comparisons. The main reason is Shell sort's low overhead compared to O(n log n) sorts like Quicksort and Mergesort. Also, it is an iterative sort, and thus it will really be a lot faster than its O(n log n) competitors. Note here that we are talking about 5,000,000 (randomized) numbers and below. Above that, I cannot tell how much they will fare. It is possible that the O(n log n) sorts will perform better once we reach array sizes in the billions or more, but I haven't proven it myself in practice.
If you want to experiment, here are a few tips to get a really efficient increment sequence for your Shell Sort:
1. Using odd numbers increases the probability that each few consecutive increments are all relatively prime. In general though, if it is possible for one to use prime numbers instead, then by all means do so. (Purely prime increments perform much better in general.)
2. The best all-purpose increment sequence I have ever used is the following increment sequence: 1, 3, 5, 11, 29, 53, 127, 263, 577, 1277, 2819, 6211, 13723, 30367, 67139, 148513, 328511, 726641, 1607321, 3555379, ... The formula used is Math.flr(1+2.211991^p) then converted to the smallest prime greater than or equal to that number, for all integers p>0. (The necessary increment 1 replaces what would have been 2 if p>=0.) One thing to note here is that it's obviously not the best choice if you want to minimize the number of swaps. Pratt's increments (form 2^p*3^q) is by far the choice of increments that yield the smallest number of swaps, but the number of passes* (comparisons, in effect) it would take you from the start until increment=1 would be overwhelmingly large that running Shell sort with Pratt's increments take twice as long to finish compared to my prescribed increments above for array size 5,000,000. The increment sequence above provides greater balance between the number of swaps and the number of comparisons. Another competitive increment sequence would be 1, 2, 3, 7, 23, 89, 257, 617, 1297, 2459, 4217, 6823, 10427, 15319, 21727, 29819, 40031, 52651, 67699, 85931, ... but my testing for these increments are yet unfinished. These increments, in general, yield approximately 11% less swaps, but 24% more comparisons compared to the sequence above beginning with 1,3,5,11,... (Figures at array size of 5,000,000.)
  • Recall:
while (k>-1) {
for (int i=increment[k]; i<Array.length; i++) {
int j=i;
int m=Array[i];
while ((j>=increment[k])&&(Array[j-increment[k]]>m)) { // <--- THIS PART! <---
Array[j] = Array[j-increment[k]];
j=j-increment[k];
}
Array[j]=m;
}
k--;
}
The part pointed to gives one comparison every iteration. Imagine how many times you have to pass through that line everytime you get a new increment. More increments yield less swaps, but there is a certain point that if you keep on adding more increments, the number of additional comparisons overwhelm the reduced number of swaps. (Law of diminishing returns.) The reason I favor my above-mentioned increment sequence beginning with 1,3,5,11,... is because the average number of comparisons is approximately 2*S+f(N) where S is the number of swaps and f(N) is a (yet unkown and unproven) sublinear function of N, the size of your array. That, by far, had the most efficient mix of swaps and comparisons I have ever seen in my tests. (My tests was compared to the standard increments available today like the original Shell's increments, Hibbard's, Sedgewick's, Knuth's, Pratt's, etc. I tweaked these increments a bit, for example by converting the increments to odd or to prime, and then tested them each time on several fixed and varying randomized arrays.)
You may verify these data yourselves by trying them on your standard programming languages (e.g., Pascal, C, C++, Java, etc.)
Another fun thing I found out about Shell sort, most especially when using the original Shellsort increments 0.5*n, 0.25*n, 0.125*n, ..., is that it runs in O(n log n) time for arrays with inversely arranged elements. It's best to watch this via animations (some can be found in the WWW), especially arrays modelled after bars, because you will see a "saw-teeth" effect. Why does it run in O(n log n) time? Imagine a Quicksort on a different array which is always able to partition the elements. Although this version of Shellsort does not put any element in-place, as would be the pivot element in Quicksort, it is guaranteed that for some k<n, those k consecutive numbers are only permutations of the same, fully sorted subarray. Thus if for Quicksort we have
T(n)=2*T(n/2) + O(n)
Here we have roughly the same amount of swaps, plus an additional (n/i) for every increment i. Since we start our increments with n/2, n/4, n/8, n/16, ..., we would have 2+4+8+16+32+...2^p additional swaps, where 2^p==n. (These would have been the pivots in its Quicksort counterpart.) There are O(lg n) increments here, so we have an average of 2*n-1 (or in this case, 2*n-2 would be more precise) additional swaps overall, and thus the complexity (number of swaps) is still O(n log n). (The sum of 2^i, i from 1 to lg n, belongs to O(n) complexity.) Best123 10:02, 18 November 2006 (UTC)

---

The sample claims to be in Java, and yet is in C.

No, it uses Java's array syntax. All it's missing is the method access qualifier. Deco 18:12, 15 December 2005 (UTC)

[edit] Stover

I didn't know about the work of Stover until a couple of days ago, when I saw it in the article. I did some tests, and it is pretty good. First, however, the Sedgewick sequence he gives in figure 3 is not as good as the Sedgewick sequence in (11) of Knuth, vol 3, 2nd ed, 5.2.1 (which is about 5% faster than the one Stover uses). Nevertheless, Stover's #7 sometimes beats the better Seqgewick sequence, but usually not. Bubba73 16:16, August 31, 2005 (UTC)

[edit] Nitrogen peroxyde ?

O(N2) means something else in the context of calculation. Please write it plain. Thanks. --DLL 12:36, 26 January 2006 (UTC)

[edit] Shell or shell ?

For many years I tried to visualize the shells, much as there are moving bubbles in bubble sort. Then I figured out that it was named after its inventor, and it was not an analogy.

Would it be worth capitalizing shell where it appears?

Not all names remain capitalized in compound words, but it seems like a lot of people who write about it do capitalize it. Perhaps we should. Deco 00:21, 3 February 2006 (UTC)

[edit] Algorithm question

First of all i think that instead of: for (j = i - gap; j >= 0 && a[j] > value; --j) there should be for (j = i - gap; j >= 0 && a[j] > value; j-=gap)


The code still yelds the correct result beacause in the final step gap=1 and the alg does an insert sort.... But in terms of complexity it won't act well


Secondly i think the algorithm should also be explained in words, most of the time this helps a lot... A similar explanation like the one in the first link of the external links section would be great. I will insert it if you guys don't mind.

I agree with your second point. However, your first point is incorrect; if we were to move j by gap, we would only sort one column of the matrix containing the list rearranged into gap columns, so the sort would not be effective. This is crucial. Deco 00:34, 19 June 2006 (UTC)

[edit] Contradiction regarding running time?

At the top of the article, it says "estimates range from O(n ^ 1.25) to O(n ^ 1.5)" - that is, it is believed to be impossible to go below n^1.25. Later it says - "Depending on the choice of gap sequence, Shellsort has a worst-case running time of ... O(n log^2 n)" - which, as far as I understand, means that a sequence is known for which it is n (ln n)^2. Does it mean something else? This is either a contradiction, or a very unclear wording which should be rewritten. Any ideas? -- Meni Rosenfeld (talk) 18:34, 18 June 2006 (UTC)

The person who wrote the 1.25 was probably unfamiliar with the sequence permitting O(nlog2n) shellsort. I've updated it. Deco 00:24, 19 June 2006 (UTC)

Now that's more like it :). Thanks. -- Meni Rosenfeld (talk) 15:00, 19 June 2006 (UTC)

[edit] Need discussion of gap insertion sort and sequence details

I've unlinked gap insertion sort in the article because this algorithm has virtually no use outside of shellsort, and is therefore most appropriate to discuss in this article (correct me if I'm wrong). We need to add discussion of gap insertion sort and of the specific sequences that produce certain asymptotic runtimes. I think it would be helpful to use the matrix characterization, where the list is rewritten as a table of k columns, where k is the gap, and the columns are sorted. Even the summary of this algorithm on the sorting algorithm page is already more complete than this article - maybe we should steal that. Deco 15:06, 19 June 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../s/h/e/Talk%7EShell_sort_97d7.html"