#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define N 23        /* ソートするものの個数 */
#define MAX 99      /* 数値データは 0 ... MAX */

#define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; }

int myrand(int max);
void print(void);
void sort(void);

int a[N];

main() {
    int i;

    srand((unsigned)time(NULL));        /* 現在時刻で乱数の種を初期化 */

    for (i=0; i<N; i++) {
        a[i] = myrand(MAX);
    }
    print();
    sort();
    print();
    return;
}


/* 0 ... max の範囲の乱数を返す。max <= RAND_MAX でなければならない */
int myrand(int max) {
    int r;

    if (max == INT_MAX) {
        return rand();
    }

    while (1) {
        r = rand();
        if (RAND_MAX % (max+1) != max && r/(max+1) == RAND_MAX/(max+1)) {
            continue;
        } else {
            return r % (max+1);
        }
    }
}


/* 配列を印字 */
void print(void) {
    int i;

    for (i=0; i<N; i++) {
        printf(" %2d", a[i]);
    }
    putchar('\n');
}


/* 配列のシェルソート */
void sort(void) {
    int gap, j, i, m;

    for (gap = 1; gap < N; gap = 3*gap+1) {
        ;
    }

    for (gap /= 3; gap > 0; gap /= 3) {
        for (j = 0; j < gap; j++) {
            for (m = 1; j+m*gap < N; m++) {
                for (i = m-1; i >= 0; i--) {    /* 以下で a[j+m*gap] を挿入 */
                    if (a[j+i*gap] > a[j+(i+1)*gap]) {
                        swap(j+i*gap, j+(i+1)*gap);
                        print();                /* swap() を呼ぶごとに印字 */
                    } else {
                        break;
                    }
                }
            }
        }
    }
}