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

#define DEBUG

#define N 13        /* ソートするものの個数 */
#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(int lo, int p, int hi);
void sort(int lo, int hi);

int a[N];

main() {
    int i;

    srand((unsigned)time(NULL));        /* 現在時刻で乱数の種を初期化 */
	printf("%s %s\n", __DATE__, __TIME__);
	for (i=0; i<N; i++) {
		a[i] = myrand(MAX);
	}
	print(-1, -1, -1);
	sort(0, N-1);
	print(-1, -1, -1);
	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);
		}
	}
}

#ifdef DEBUG
/* 配列を印字。a[lo], a[p], a[hi] には印がつく */
void print(int lo, int p, int hi) {
	int i;

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

#else
/* 配列を印字 */
void print(int lo, int p, int hi) {
	int i;

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

#endif


/* 配列のクイックソート */
void sort(int lo, int hi) {
	int i, p, mi, pivot;

	if (lo < hi) {
		mi = (lo + hi) / 2;
		pivot = a[mi];
		a[mi] = a[lo];      /* a[lo] は空いたと思おう */
		i = p = lo + 1;

		/* j < p ならば a[j] < pivot であり p <= j < i ならば >= pivot */
		while (i <= hi) {
			if (a[i] < pivot) {
				swap(p, i);     /* p == i なら何もしないに等しい */
				p++;            /* swap(p++, i) は不可（マクロなので） */
			}
			i++;
		}

		a[lo] = a[p-1];
		a[p-1] = pivot;
		print(lo, p-1, hi);             /* 確認のため印字 */
		sort(lo, p-2), sort(p, hi);     /* a[p-1] が pivot であることに注意 */
	}
}