#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "util.h"

typedef int T;

void
shellsort(T a[], size_t n)
{
	//static const size_t gaps[] = { 701, 301, 132, 57, 23, 10, 4, 1 };

	// Wikipedia:
	//static const size_t gaps[] = { 2147483647, 1131376761, 410151271, 157840433, 58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1 };

	// https://www.cs.princeton.edu/~rs/shell/paperF.pdf
	static const size_t gaps[] = { 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 };

	for ( size_t k = 0; k < NELEM(gaps); ++k ) {
		const size_t gap = gaps[k];

		for ( size_t i = gap; i < n; i++ ) {
			size_t j    = i;
			T      temp = a[i];

			for ( ; j >= gap && a[j - gap] > temp; j -= gap )
				a[j] = a[j - gap];

			a[j] = temp;
		}
	}
}

static void
test(T a[], size_t n)
{
	for ( size_t i = 1; i < n; ++i ) {
		if ( a[i - 1] > a[i] ) {
			fprintf(stderr, "Error\n");
			exit(EXIT_FAILURE);
		}
	}
}

int
main(void)
{
	T a[1000000];

	srand(time(NULL));
	for ( size_t i = 0; i != NELEM(a); ++i )
		a[i] = rand() % 1000;

	clock_t start = clock();
	shellsort(a, NELEM(a));
	clock_t end = clock();

	test(a, NELEM(a));

	printf("duration: %.3f sec\n", ((double) (end - start)) / CLOCKS_PER_SEC);

	return EXIT_SUCCESS;
}