언제나 처음처럼

#include <iostream>
using namespace std;

// 원소 교환
void swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

// 선택정렬 
// time complexity : O(n^2)
void selectionSort(int arr[], int len) {
	for (int i = 0; i < len; i++) {
		int idx = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[idx] >= arr[j])
				idx = j;
		}

		swap(arr, i, idx);
	}
}

// 삽입정렬 
// 정렬 되어있는 경우 time complexity : O(n)
// 정렬 되어있지 않는 경우 time complexity : O(n^2);
void insertionSort(int arr[], int len) {
	for (int i = 1; i < len; i++) {
		int val = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (val < arr[j]) {
				arr[j + 1] = arr[j];
				arr[j] = val;
			}
			else {
				break;
			}
		}
	}
}

// 버블정렬
// time complexity : O(n^2)
void bubbleSort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++) {
		for (int j = 0; j < len - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
			}
		}
	}
}

// 퀵정렬
// 평균, 최고 time complexity : O(n log n)
// 최악 time complexity : O(n^2) <--- 최적화 전
// 퀵정렬 최적화 -> left, mid, right 값 중에서 중간값을 pivot으로 선택하도록 구현
// 선택한 pivot과 left 값을 서로 바꾼다
int getMidIndex(int arr[], int left, int right) {
	int mid = (left + right) / 2;
	int idx[3] = { left, mid, right };

	if (arr[idx[0]] > arr[idx[1]]) {
		swap(idx, 0, 1);
	}

	if (arr[idx[1]] > arr[idx[2]]) {
		swap(idx, 1, 2);
	}

	if (arr[idx[0]] > arr[idx[1]]) {
		swap(idx, 0, 1);
	}

	return idx[1];
}

void quickSort(int arr[], int left, int right) {
	if (left >= right) return;

	int pIdx = getMidIndex(arr, left, right);
	swap(arr, left, pIdx);

	int pivot = left;
	int low = left + 1;
	int high = right;

	while (1) {
		while (low <= right && arr[low] <= arr[pivot])
			low++;
		while (high > left && arr[high] >= arr[pivot])
			high--;

		if (low > high) // low, high 가 서로 교차했다면
			break;

		int temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
	}

	int temp = arr[pivot];
	arr[pivot] = arr[high];
	arr[high] = temp;

	quickSort(arr, left, high - 1);
	quickSort(arr, high + 1, right);
}

// 병합정렬
// time complexity : O(n log n)
// 정렬한 배열을 임시로 저장할 임시 메모리가 필요한 단점이 있다
// 정렬의 대상이 배열이 아닌 리스트일 경우 임시 메모리 필요 없어서 좋은 성능 발휘
void merge(int arr[], int left, int mid, int right) {
	int idx1 = left;
	int idx2 = mid + 1;

	int* temp = new int[right + 1];
	int idx = left;

	while (idx1 <= mid && idx2 <= right) {
		if (arr[idx1] < arr[idx2]) // idx1이 가리키는 값이 idx2가 가리키는 값보다 작다면
			temp[idx++] = arr[idx1++];
		else
			temp[idx++] = arr[idx2++];
	}

	if (idx1 > mid)
		while (idx2 <= right)
			temp[idx++] = arr[idx2++];
	else
		while (idx1 <= mid)
			temp[idx++] = arr[idx1++];

	for (int i = left; i <= right; i++)
		arr[i] = temp[i];

	delete[] temp;
}

void mergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;

		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);

		merge(arr, left, mid, right);
	}
}


int main(void) {
	int arr[10] = { 3,4,5,6,1,10,2,7,8,9 };

	//	selectionSort(arr, 10);
	//	insertionSort(arr, 10);
	//	bubbleSort(arr, 10);
	//	quickSort(arr, 0, 9);
	mergeSort(arr, 0, 9);

	for (auto x : arr)
		cout << x << ' ';
}