Re: [RFC] 2.5.8 sort kernel tables

Jamie Lokier (lk@tantalophile.demon.co.uk)
Fri, 19 Apr 2002 14:45:22 +0100


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/