#include "..\CookHeader.h"

Array <int> dataAry = { 120, 120, 188, 150, 168, 50, 50, 162, 105, 120, 177, 50 };

Array <int> quickSort(Array <int> ary) {
	int n = len(ary);
	if (n <= 1)				// 정렬할 리스트의 개수가 1개 이하면
		return ary;

	int pivot = ary[n / 2];	// 기준 값을 중간값으로 지정
	Array <int> leftAry, midAry, rightAry;

	for (int i = 0; i < n; i++) {
		int num = ary[i];
		if (num < pivot)
			leftAry.push_back(num);
		else if (num > pivot)
			rightAry.push_back(num);
		else
			midAry.push_back(num);
	}

	Array <int> retLeft, retRight;
	retLeft = quickSort(leftAry);  // 왼쪽 배열 재귀
	retLeft.insert(retLeft.end(), midAry.begin(), midAry.end());	// 왼쪽 + 중간
	retRight = quickSort(rightAry);	// 오른쪽 배열 재귀
	retLeft.insert(retLeft.end(), retRight.begin(), retRight.end());// 왼쪽 + 오른쪽 --> 왼쪽에 대입
	return retLeft;
}

int main() {
	print("정렬 전 -->");
	printArray(dataAry);
	dataAry = quickSort(dataAry);
	print("정렬 후 -->");
	printArray(dataAry);
}