#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<cstdlib>

int N, i, j, k, s, x, m;

void shellsort(int a[]){

    int h[4];
    h[0] = 9;
    h[1] = 5;
    h[2] = 3;
    h[3] = 1;
    for(m=0; m<4; m++){
        k = h[m];
        s = -k;
        for(i = k; i<N; i++){
            x = a[i+9];
            j = i-k;
            if(s==0) s = -k;
            s = s+1;
            a[s+9] = x;
            while(x < a[j+9]){
                a[j+k+9] = a[j+9];
                j = j-k;
            }
            a[j+k+9] = x;
        }
    }
}


int main(){
    N = 10;
    int a[N+9];

    srand(time(NULL));
    for(i=0; i<N+9; i++) a[i] = rand();

    for(i=9; i<N+9; i++) printf("%d  ", a[i]);
    printf("\n");
    shellsort(a);
    for(i=9; i<N+9; i++) printf("%d  ", a[i]);


    //for(i=9; i<N+9; i++) printf("[%d]: %d\t", (i-10), a[i]);
    getch();
    return 0;
}