Messages in this thread | | | Date | Fri, 19 Apr 2002 14:45:22 +0100 | From | Jamie Lokier <> | Subject | Re: [RFC] 2.5.8 sort kernel tables |
| |
Oliver Xymoron wrote: > Combsort is a trivial modification of bubblesort that's O(n log(n)). > > http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm
Cute. Combsort is very closely related to Shellsort, which is tiny, fast and old (c.1959), yet its time complexity is still not well understood:
http://www.cs.princeton.edu/~rs/shell/shell.c http://www.cs.princeton.edu/~rs/shell/
The above paper mentions a variant of Shellsort which uses a "h-bubble" operation. Beware! That does probabilistic sorting, which means "nearly always sorts, with high probability"!
I think that Combsort is equivalent to that variant of Shellsort, with larger constant factors in its time complexity (because bubbling is slower than insertion), and it effectively degrades to Bubblesort in the event that the probabilistic h-bubble Shellsort fails to sort.
There are a couple of improvements to h-bubble Shellsort mentioned in the paper which may be faster.
enjoy, -- Jamie - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |