5 ms·
Comb Sort - Just As Good As Quick Sort
- dasht 17y agoSorry if this is too meta but: I usually think the wikipedia.org items on HN are just a silly waste of time (e.g, not news) but I do have to admit that this one got me. Neat algorithm. Hadn't heard of it prior and wouldn't have thought of it spontaneously.
- drallison 17y agoI like the occasional wikipedia article on HN. They are often illuminating and amusing.
- wcarss 17y agoThe guy who originally devised the algorithm is a professor at the University of Guelph, in Ontario, Canada. He's a pretty interesting professor - escaped from being drafted into the Polish army during World War II, wrote some of TCP at Stanford in the 70's, somehow ended up teaching networking, operating systems, and some other random subjects in an off-the-beaten-path Canadian school that's mostly known for farming. I'm a student there; it's neat to see an article about his creation pop up. :)
- statistic 17y agoHeh. I was excited to see it as well. I originally thought you had posted it when I saw it.
- pmiller2 17y agoDoes anyone know of a proof that this really is an $O(n log n)$ sort? I can sort of see it intuitively, but I can't quite convince myself it is true.
- asmosoinio 17y agoI'd guess it is generally O(n log n) for random data, but not mathematically. At least seems to me that an for an inverted range (n, n-1, n-2, ... 0) the algorithm will come down to O(n^2). I could be wrong though, didn't really think about it for that long. Edit: I might be in the wrong here. I did some quick tests with this code (http://yagni.com/combsort/combsort.py http://yagni.com/combsort/combsort.py) and did not find it to be much slower when data is a reversed range vs. sorted range. So much for that intuitive thought.
- deleted 17y ago[deleted]
- sorbits 17y agoIt is not O(n log n) — neither is quicksort for that matter :) The comb sort is intuitively O(n²). The inner loop will run n - gap iterations, where gap starts at n / 1.25 and decrease toward 1. I think we can effectively count this as O(n). The outer loop is more tricky, in the worst case it will run until n < 1.25^m (where m is number of iterations). Edit: Just re-read the algorithm and I overlooked that the outer loop stops when gap is below one AND no swaps were performed, so the above is optimistic. I.e. it is very clearly O(n²) and if you want to be exact, it could actually be something like O(n × (n + log n)) (for a shrink factor of 2, to make it simple) — but more detailed study of the algorithm is required to arrive at the exact worst running time, as the “preprocessing” (where gap > 1 is going to affect how many swaps can be performed when gap = 1).
- moultano 17y agoI'm going to need some citations before I believe that it's just as good as quick sort.
- gjm11 17y agoThe article neither claims, nor offers any evidence, that comb sort is "just as good as quick sort"; could someone fix the title here, please? I'd guess that it probably performs about as well as Shell sort: hard to analyse, strongly dependent on the detail of how your increments are chosen, typically worse than O(n log n).