Sorting algorithms benchmark

[Deewiant]

Stewart Gordon wrote:
> Deewiant Wrote:
> <snip>
>> I took a more detailed (but still quite cursory) look at your 
>> code, and it seems you do things differently from the 
>> "traditional" method.  I'm not sure if that's even equivalent 
>> to the normal comb sort.
> 
> What do you consider to be the "normal comb sort"?  OK, so the call to lastSwapBubbleSort was my idea, but other than that, there doesn't seem to be any difference at all, at least from this:
> 
> http://en.wikipedia.org/wiki/Comb_sort
> 

That's exactly what's confusing me. I suppose the reason you need that call is
that you're not counting the number of swaps made in the loop, and you're
stopping just when the gap is 1, not when swaps are also zero. Which I think
makes the algorithm a bit different, since the number of "combs" you do is
limited to once per gap size, plus the one bubble sort after you're done.

I added my comb sort 11 implementation to your benchmark, and it's noticeably
faster for random data than your comb sort, at least on my machine. So
something's different, to be sure. Even without the optimization related to gap
size 11, mine is faster.

Here's the source, changed to work with your benchmark, if you're interested:

void combSort11(uint[] a)
out {
	debug (100) printList(a);
	checkSorted(a);
} body {
	// empirically found to be good at:
	// http://world.std.com/~jdveale/combsort.htm
	// 1 / (1 - 1 / (e ^ phi)), phi being golden ratio = (sqrt(5) + 1)/2
	const real SHRINK_FACTOR = 1.2473309501039786540366528676643474234433714124826L;

	bit swapped = false;
	size_t gap = a.length;

	do {
		if (gap > 1) {
			gap = cast(size_t)(cast(real) gap / SHRINK_FACTOR);

			// hence, comb sort 11
			if (gap == 9 || gap == 10)
				gap = 11;
		}

		swapped = false;

		for (size_t i = 0; i < a.length - gap; ++i) {
			size_t j = i + gap;

			if (a[i] > a[j]) {
				swap(a[i], a[j]);
				swapped = true;
			}
		}

	} while (swapped || gap > 1);
}

-- 
Remove ".doesnotlike.spam" from the mail address.