#include <GConsoleLib.h>
#include <stdio.h>

void DrawGraph(int);	//関数プロトタイプ宣言
void BSort();
void QSort(int, int);

int kazu[] = { 72, 13, 62, 22, 15, 98, 36, 46, 31, 4 };

int main() {
	gfront();
	gcls();

	gcolor(200, 200, 200);
	gbox(40, 40, 560, 400);

	//BSort();		//バブルソート
	QSort(0, 9);	//クイックソート
}

//バブルソート
void BSort() {
	glocate(0, 0); gcolor(0, 0, 0);
	gprintf("バブルソート");
	for (int k = 9; k > 0; k--) {
		//printf("%d度目\n", 10 - k);
		for (int j = 0; j < k; j++) {
			if (kazu[j] > kazu[j + 1]) {
				//入れ替え
				int temp = kazu[j];
				kazu[j] = kazu[j + 1];
				kazu[j + 1] = temp;
				//表示
				DrawGraph(j);
			}
		}
	}
}

//クイックソートの分割処理
int partition(int left, int right) {
	int i = left;
	int j = right - 1;
	int pivot = kazu[right];	//右端を軸にする
	int temp;
	while (1) {
		while (kazu[i] < pivot) i++;
		while (i < j && pivot < kazu[j]) j--;

		if (i >= j) break;	//ループ脱出
		//iとjの要素を交換
		temp = kazu[i];
		kazu[i] = kazu[j];
		kazu[j] = temp;
		//表示
		DrawGraph(i);
	}
	//枢軸とiの要素を入れ替え
	temp = kazu[i];
	kazu[i] = kazu[right];
	kazu[right] = temp;
	DrawGraph(i);
	return i;
}

//クイックソート
void QSort(int left, int right) {
	glocate(0, 0); gcolor(0, 0, 0);
	gprintf("クイックソート");

	//要素が1つのみになったら終了
	if (left >= right) return;

	//分割処理
	int pivot = partition(left, right);

	QSort(left, pivot - 1);	//左側を整列（再帰呼び出し）
	QSort(pivot + 1, right);	//右側を整列
}

void DrawGraph(int target) {
	for (int i = 0; i < 10; i++) {
		int y = 60 + i * 36;
		int w = kazu[i] * 5;
		if (i == target) gcolor(255, 128, 0);
		else gcolor(0, 128, 255);
		gbox(60, y, w, 32);
		gcolor(200, 200, 200);
		gbox(60 + w, y, 540 - w, 36);
		//printf("%d\t", kazu[i]);
	}
}