#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]);
	}
}