#include "..\CookHeader.h"

Array <int> bubbleSort(Array <int> ary) {
	int n = len(ary);
	for (int end = n-1; end > 0; end--) {
		bool changeYN = false;
		for (int cur = 0; cur < end; cur++) {
			if (ary[cur] > ary[cur+1]) {
				int tmp = ary[cur + 1];
				ary[cur + 1] = ary[cur];
				ary[cur] = tmp;
				changeYN = true;
			}
		}
		if (!changeYN)
			break;
	}
	return ary;
}

void qSort(Array <int>& arr, int start, int end) {
	if (end <= start)
		return;

	int low = start;
	int high = end;

	int pivot = arr[(low + high) / 2];	
	while (low <= high) {
		while (arr[low] < pivot)
			low++;
		while (arr[high] > pivot)
			high--;
		if (low <= high) {
			int temp = arr[low];
			arr[low] = arr[high];
			arr[high] = temp;
			low++;
			high--;
		}
	}

	int mid = low;

	qSort(arr, start, mid - 1);
	qSort(arr, mid, end);
}

void quickSort(Array <int>& ary) {
	qSort(ary, 0, len(ary) - 1);
}

int main() {
	Array <int> tempAry;
	Array <int> bubbleAry, quickAry;

	randomInit(1000000, 9999999); // 1000000 ~ 9999999 랜덤 데이터 생성
	for (int r = 0; r < 10000000; r++) {
		int num = cookRandom(gen);
		tempAry.push_back(num);
	}
	sortArray(tempAry); // C++ 정렬 기능
	int rndPos = rand() % len(tempAry);
	println("# 데이터 개수 --> " + to_string(len(tempAry)));
	println("# 끼어든 위치 --> " + to_string(rndPos));
	insertArray(tempAry, rndPos, tempAry[len(tempAry) - 1]);

	copyArray(tempAry, bubbleAry);	// 복사
	copyArray(tempAry, quickAry);	// 복사

	time_t start, end;
	start = clock();
	bubbleSort(bubbleAry);
	end = clock();
	println("다시 정렬 시간(버블 정렬) -->" + to_string((end - start) / 1000.0) + "초");

	start = clock();
	quickSort(quickAry);
	end = clock();
	println("다시 정렬 시간(퀵 정렬) -->" + to_string((end - start) / 1000.0) + "초");
}