Sorting algorithms benchmark

[Deewiant]

Stewart Gordon wrote:
> I've written a program to benchmark a number of sorting algorithms.
> 
> http://pr.stewartsplace.org.uk/d/sortbench.d
> 
> It includes options to output the timings to a CSV file and to control the number of tests of each algorithm to perform (likely to be needed on modern machines).
> 
> Stewart.
> 

Nice. One of the very first D programs I wrote was a class Sorter which aimed to
do the same, but I never published it since most of the code was just pretty
much directly copied from somewhere. Besides, I didn't really understand most of
the algorithms, and couldn't get all the ones I wanted to work. Pigeonhole sort,
in particular, couldn't reliably work for all types without opAssign
overloading, which was necessary.

Some comments from what I do (think I do) know, however:

Your comb sort uses a shrink factor of 0.7. Comb sort 11 uses 1 / (1 - 1 / (e ^
phi)), where e is Napier's constant and phi the golden ratio. This leads to
possible optimization in the algorithm.

But alas, the page that used to contain the article describing it is gone from
the web: http://world.std.com/~jdveale/combsort.htm. Dammit! I haven't copied
the source code for it from there, either. Oh well, a less optimal version but
still, I wager, better than yours: http://yagni.com/combsort/index.php#cpp-combsort

What I used: const real SHRINK_FACTOR =
1.2473309501039786540366528676643474234433714124826;

You're missing shell sort: http://en.wikipedia.org/wiki/Shell_sort
See also: http://www.cs.princeton.edu/~rs/talks/shellsort.pdf
My 1.5-year old code (no idea how it works - I'm particularly frightened of the
bit math, I think it's the formula here:
http://www.research.att.com/~njas/sequences/A033622) is at the bottom of this
post, if you want to have a look.

Other sorts that could be added:
	- Gnome sort, http://en.wikipedia.org/wiki/Gnome_sort
	- Introspective sort: http://en.wikipedia.org/wiki/Introsort
	- Three-way merge sort:
http://www.cs.queensu.ca/home/cisc121/2002w/assignments/assn8/solution/MergeThreeWay.java
	- Counting sort, http://en.wikipedia.org/wiki/Counting_sort
	- Bucket sort, http://en.wikipedia.org/wiki/Bucket_sort
	- Pigeonhole sort, http://en.wikipedia.org/wiki/Pigeonhole_sort

I didn't look too much at your radix sorts, they might have a lot in common with
the last three of the above.

Also, your "buffered insertion sort" is perhaps more commonly known as "binary
insertion sort", since you mention it uses binary search.

--

// TYPE is just a template parameter
// comp defaults to a simple less-than comparison
// the inout is probably unnecessary, I wouldn't have known that back then
void shellSort(inout TYPE[] a, size_t beg = 0, size_t end = 0, cmpType cmp = null) {
	if (cmp is null) cmp = this.comp;
	if (end == 0) end = a.length;

	// can't figure out how to get it working for arbitrary beg and end, hence kept
separate here
	void actualShellSort(inout TYPE[] ra) {
		size_t h = 1, hh = 1;
		while (h < ra.length) {
			// magic numbers from formula:
			//
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A033622
			if (hh % 2)
				h = 8 << hh - 6 << ((hh + 1) / 2) + 1;
			else
				h = 9 << hh - 9 << ( hh      / 2) + 1;
			++hh;
		}

		while (h > 0) {
			// for each set, of which there are h
			for (size_t i = h - 1; i < ra.length; ++i) {
				// pick last element in set
				TYPE tmp = ra[i];
				size_t j = i;

				// compare tmp to the one before it in the set
				// if they are not in order, continue this loop, moving
				// elements back to make room for tmp
				for (; j >= h && !cmp(tmp, ra[j-h]); j -= h)
					ra[j] = ra[j - h];

				ra[j] = tmp;
			}

			// all h-sets sorted
			h /= 3;
		}
	}

	if (!smartToSort(a, beg, end, cmp)) return;

	TYPE[] foo = a[beg..end];
	foo.actualShellSort();
}

// other relevant stuff to get the above to compile (not tested, though):

bit smartToSort(inout TYPE[] a, size_t beg, size_t end, cmpType cmp) {
	if (end <= beg)
		return false;
	if (end - beg > a.length)
		return false;

	if (end - beg < 2)
		return false;
	else if (end - beg == 2) {
		if (!cmp(a[end - 1], a[beg]))
			a.swap(beg, end - 1);
		return false;
	}

	return true;
}

alias int function(in TYPE left, in TYPE right) cmpType;