Dyadic shellsort

shellsort.cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cassert>
using namespace std;

int count; // to experiment a bit...

// divide and conquer shellsort with powers of two...
template <class T>
void go(vector < T > & v, int d, int r)
{
	int N = v.size(), q = (N-r) / d + !!((N-r)%d);
	// if there is 1 or less elements present, nothing to sort.
	if ( q <= 1)	return;
	// breaks into two possible remainders mod (2d)
	go(v,2*d,r); go(v,2*d,r+d);
	// insertion sort now
	// within { v[d*k+r] : k }
	for (int k = 1; d*k+r < N; k++)
	{
		T val = v[d*k+r];
		for (int j = k - 1; j >= 0; j--)
		{
			if (val < v[d*j+r] )
				v[d*(j+1)+r] = v[d*j+r], count++;
			else
			{
				v[d*(j+1)+r] = val;
				goto nxt;
			}
		}
		v[r] = val; // in case it was the smallest
		nxt:;
	}
}

template <class T>
void shell_sort(vector < T > & v)
{
	go(v,1,0);
}

// testing a bit...
int main(void)
{
	srand(time(NULL));
	int M = 100000;
	int iter = 100;
	vector <int> v(M);
	long long avg = 0;
	for (int j = 0; j < iter; j++)
	{
		count = 0;
		for (int i = 0; i < M; i++)
			v[i] = rand() % M;
		shell_sort(v);
		cerr  << "Number of comparisons: " << count << endl;
		avg += count;
	}
	cerr << (avg / (double)iter) << endl;
	return 0;
}