#include <stdio.h>

#define SIZE_OF_ARRAY(array)    sizeof(array)/sizeof(array[0])

static void shell_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
	int array[] = {7, 2, 4, 5, 1, 6};

	print_array( array, SIZE_OF_ARRAY(array) );
	shell_sort( array, SIZE_OF_ARRAY(array) );
	print_array( array, SIZE_OF_ARRAY(array) );

	return 0;
}

/*
	?????§???????????? (??????)
*/
void shell_sort(int* array, size_t size)
{
	size_t i, j;
	size_t h, h_tmp;
	int tmp;


	/* ??????????????? h ????±??????? */
	/* 1,4,13,40,121... ???????????????1 ???????§??????? h=h*3+1 ???????????????????????????
	   ???????????????????????§???size / 9 ????¶??????????????????§????????????????????? h ??¨?????????*/
	h = 1;
	for( h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
		h = h_tmp;
	}

	while( h > 0 ){
		for( i = h; i < size; ++i ){
			tmp = array[i];
			for( j = i; j >= h && array[j-h] > tmp; j -= h ){
				array[j] = array[j-h];
			}
			array[j] = tmp;
		}
		h /= 3;  /* ?????????????????? */
	}
}

/*
	?????????????´??????????
*/
void print_array(const int* array, size_t size)
{
	size_t i;

	for( i = 0; i < size; ++i ){
		printf( "%d ", array[i] );
	}
	printf( "\n" );
}