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

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+1; i<N; i++){
            x = a[i];
            j = i-k;
            if(s==0) s = -k;
            s = s+1;
            a[s] = x;
            while(x < a[j]){
                a[j+k] = a[j];
                j = j-k;
            }
            a[j+k] = x;
        }
    }
}


int main(){
    N = 1000;
    int a[N];

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

    shellsort(a);

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