Combsort's useage varies with the comb gapsize offset, so I suspect some of those empty fields might need "varies" as opposed to O notation responses. The most optimized gapsize I've ever seen offered is at http://world.std.com/~jdveale/combsort.htm and uses a table. Alternatively, the original version ( http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm ) uses /=1.3 instead. I suspect that the other number, /='1.279604943109628' , is more precise.
How in depth should these encyclopedia articles be? Another entry could be Hybrid Sort which uses Quicksort on lists larger than 6 elements and switches to Bubblesort when the Quicksort divisions are small enough (6 or less elements), because on very small lists Bubblesort is actually faster. Then there are the many specialized methods for special data. Examples are Bentley Sedgewick, Sadakane's algorithm, and Forward Radix Sort for the sorting of all suffixes of a string as is required for the Burrows Wheeler Transform.
Also, the algorithms should be split into two groups: the comparison based ones that cannot be faster than n log n but do not need additional knowledge of the data, these being Quick Sort, Heap Sort, Merge Sort, Bubble Sort, etc., and the ones that do depend on the data being within a range of values or otherwise comparable to an external reference, these being Bucket Sort and Radix Sort.
How is this different to shell sort?
Search Encyclopedia
|
Featured Article
|