#include <iostream>
using namespace std;

template <class T>
void ShellSort(T a[], int N)
{
?for (int gap = N/2; gap; gap = gap/2)
?{
??for (int i = gap; i < N; i++)
??{
???T temp = a[i];
???int j;
???for (j = i; j >= gap && temp < a[j - gap]; j -= gap)
???{
????a[j] = a[j - gap];
???}
???a[j] = temp;
??}
?}
}

template <class T>
void output(T a[], int N)
{
?for(int i=0; i<N; i++)
?{
??cout << i << ":" << a[i] << endl;
?}
}

int main()
{
?int a[] = {3,3,1,0,2,2,1,9,8,3,1,1,2,6,1,2,7,8};
?output(a, sizeof(a)/sizeof(int));
?ShellSort(a, sizeof(a)/sizeof(int));
?output(a, sizeof(a)/sizeof(int));
?
?//end:
?int end;
?cin >> end;
?return 0;
}