#include <iostream>
using namespace std;
void printArr(int n,int a[]){
    for (int i=0; i<n; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

void directInsertSort(int dk,int n,int a[]){
    for (int i = dk; i<n; i++) {
        if (a[i]<a[i-dk]) {
            int x = a[i];
            int j = i-dk;
            while (x<a[j]) {
                a[j+dk] = a[j];
                j = j-dk;
            }
            a[j+dk] = x;
        }
    }
    printArr(n,a);
}

void shellSort(int n,int a[]){
    int dk = n/2;
    while (dk>=1) {
        directInsertSort(dk,n, a);
        dk = dk/2;
    }
}
int main(int argc, const char * argv[]) {
    int a[] = {2,4,5,1,9,8,6,4,5};
    shellSort(9, a);
    return 0;
}