#include <iostream>

using namespace std;

void printArray(int* arr, int len);
void shellSort(int *arr, int len);

int main()
{
	int arr[] = {1, 4, 3, 10, 4, 7, 2, 5};
	int len = sizeof(arr)/sizeof(*arr);

	printArray(arr, len);
	shellSort(arr, len);
	printArray(arr, len);

	cin.get();
	return 0;
}

void shellSort(int *arr, int len)
{
	int i, gap;
	for(gap = len /2; gap > 0; gap /= 2)
	{
		for(i = gap; i < len; i++)
		{
			if (arr[i] < arr[i - gap])
			{
				int tmp = arr[i];
				int j = i - gap;
				while(j >= 0 && tmp < arr[j])
				{
					arr[j + gap] = arr[j];
					j -= gap;
				}
				arr[j + gap] = tmp;
			}
		}
	}	
}

void printArray(int* arr, int len)
{
	for(int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}
//cpp/8812