2002-01-06
Home Page
Journal
2002
2002-01-01
2002-01-06
2002-01-13
2002-01-26
2002-01-31
2002-02-01
2002-02-09
2002-02-16
2002-02-23
2002-04-06
Robert Sedgewick in his Algorithm book wrote:
Shellsort is the method of choice for many sorting applications because it has acceptable running time even for moderately large files (say, less than 5000 elements) and requires only a very small amount of code that is easy to get working. We'll see methods that are more efficient in the next few chapters, but they're perhaps only twice as fast (if that much) except for large N, and they're significantly more complicated. In short, if you have a sorting problem, use [Shellsort], then determine whether the extra efort required to replace it with a sophisticated method will be worthwhile.
While Shellsort is better than bubblesort or insertion sort for temporary sort, why not use quicksort directly if that proved to be easy? You can use a simple implementation of quicksort, then optimize it as needs arise. Sedgewick continued with:
A carefully tuned version of Quicksort is likely to run significantly faster on most computers than any other sorting method. ... But if one is not willing to invest the effort to be sure that a Quicksort implementation is not flawed, Shellsort might well be a safer choice that will perform quite well for less implementation effort.
Having seen optimized shellsort, I can definitely say that shellsort isn't that easy. Combsort, which is bubble sort with large bubble is much easier, and not much slower. In fact, you can say that shellsort is sort of heavy duty version of insertion sort, which in turn is optimized version of bubble sort.
Since quicksort discovery by C. A. R. Hoare in 1960, much has been analyzed of its performance. I'm disappointed that no one has yet to show how easy it is to do quicksort, until I came along. How simple can a quicksort be? Four lines.