분할 정복을 활용한 대표적인 정렬은 대표적으로 병합정렬(Merge Sort), 큌정렬(Quick Sort) 두 가지가 있습니다.
이 두가지 정렬은 시간 복잡도가 NlogN으로 정렬 알고리즘 중에서 효율성이 좋습니다.

1. 병합 정렬(Merge Sort)

1. 분할
2. 정복
3. 통합
   세가지로 나눌 수 있다.
   분할 : 절반씩 잘라 두 개의 리스트로 나눕니다.
   정복 : 생성된 두개의 리스트를 Merge Sort 알고리즘을 재귀 호출하여 정렬합니다.
   통합 : 정렬된 두개의 리스트를 하나의 리스트로 Merge합니다.

코드

#include <iostream>
using namespace std;

constexpr size_t MAX_N = 100000;

int a[MAX_N], buffer[MAX_N];

void merge(int* begin, int* mid, int* end) {
	int* begin1 = begin, * end1 = mid;
	int* begin2 = mid, * end2 = end;
	int* result = buffer;
	while (begin1 != end1 && begin2 != end2) {
		*result++ = *begin1 <= *begin2 ? *begin1++ : *begin2++;
	}
	while (begin1 != end1) *result++ = *begin1++; // 왼쪽이 남으면
	while (begin2 != end2) *result++ = *begin2++; // 오른쪽이 남으면

	memcpy(begin, buffer, sizeof(int) * (end - begin)); // 정렬되어있는 것을 복사하는 과정 (통합 과정)
}

void merge_sort(int* begin, int* end) {
	if (end - begin <= 1)return;
	int *mid = begin + (end - begin) / 2;
	merge_sort(begin, mid); // 분할 과정
	merge_sort(mid, end);
	merge(begin, mid, end); // 정복 과정
}

int main() {
	int arr[5]={1,8,9,6,5};
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << ' ';
	}
	cout << '\n';
	merge_sort(arr, arr + 5);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << ' ';
	}
}

출력화면

---

2. 퀵 정렬(Quick Sort)

1. index 0을 피봇으로 정합니다.
2. pivot보다 작은 원소는 좌측으로 pivot보다 큰 원소는 우측으로 이동합니다.
3. pivot을 제외하고 좌측 리스트와 우측 리스트를 재귀 호출하여 정렬합니다.

• 평균적으로 NlogN의 시간복잡도를 가지지만 최악의 경우 N^2의 시간 복잡도를 가집니다.

코드

#include <iostream>
using namespace std;

void quick_sort(int* data, int start, int end) {
	if (start >= end)return;
	int pivot = start; // 시작점을 피봇으로 설정
	int i = pivot + 1;
	int j = end;
	int temp;
	while (i <= j) {
		while (i<=end && data[i] <= data[pivot]) { // pivot보다 큰값을 찾습니다.
			i++;
		}
		while (j > start && data[j] >= data[pivot]) { // pivot보다 작은 값을 찾습니다.
			j--;
		}
		if (i > j) { // 엇갈릴 경우
			swap(data[j], data[pivot]); // 피봇과 j를 바꿔줍니다. 
		}
		else { // 엇갈리지 않을 경우
			swap(data[i], data[j]); // i, j를 바꿔줍니다.
		}
	}
	quick_sort(data, start, j - 1); // 피봇 제외하고 분할계산
	quick_sort(data, j + 1, end);
}



int main() {
	int data[10] = { 4,1,2,3,9,7,8,6,10,5 };
	for (int i = 0; i < 10; i++) {
		cout << data[i] << ' ';
	}
	cout << '\n';
	quick_sort(data,0,9);
	for (int i = 0; i < 10; i++) {
		cout << data[i] << ' ';
	}
	return 0;
}

출력화면