#include "..\CookHeader.h"

Array <int> selectionSort(Array <int> ary) {
	int n = len(ary);
	for (int cycle = 0; cycle < n - 1; cycle++) {
		int minIdx = cycle;
		for (int i = cycle+1; i < n; i++) {
			if (ary[minIdx] > ary[i])
				minIdx = i;
		}
		int tmp = ary[cycle];
		ary[cycle] = ary[minIdx];
		ary[minIdx] = tmp;
	}
	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> countAry = { 1000, 10000, 20000, 40000 };
	Array <int> selectAry, quickAry;
	
	for (int i = 0; i < len(countAry); i++) {
		randomInit(10000, 99999);	// 랜덤 데이터 생성
		selectAry.clear();
		quickAry.clear();
		for (int r = 0; r < countAry[i]; r++) {
			int num = cookRandom(gen); 
			selectAry.push_back(num);
			quickAry.push_back(num);
		}
		time_t start, end;
		println("## 데이터 수 : " + to_string(countAry[i]) + " 개");
		start = clock(); 
		selectionSort(selectAry);
		end = clock();
		println("선택 정렬 -->" + to_string((end - start)/1000.0) + "초");
		start = clock();
		quickSort(selectAry);
		end = clock();
		println("퀵 정렬   -->" + to_string((end - start)/1000.0) + "초");
		println("");
	}
}