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

int N, i, j, k, s, x, m, h[4];

void shellsort(int a[]){

    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 = 100;
    int a[N+9];

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

    shellsort(a);

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