[0x0E] 정렬 I

병합 정렬 (Merge Sort)

 

분할 정복을 이용한 정렬이다. 분할하는 과정에서 O(N), 합치는데 O(NlogN)이 소요되므로 O(NlogN)이다.

언제나 O(NlogN)이 보장된다.

숫자를 임시로 저장할 공간이 추가로 필요하기 때문에 공간복잡도는 O(N)이다.

 

1. 주어진 리스트를 두개로 나눈다.

2. 나눈 리스트 2개를 정렬한다.

3. 정렬된 두 리스트를 합친다.

 

#include <iostream>

using namespace std;

int n = 10;
int arr[1000001] = { 15, 25, 22, 357, 16, 23, -53, 12, 46, 3 };
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en) {
	int mid = (st + en) / 2;
	int lidx = st;
	int ridx = mid;

	for (int i = st; i < en; ++i)
	{
		if (ridx == en) tmp[i] = arr[lidx++];
		else if (lidx == mid) tmp[i] = arr[ridx++];
		else if (arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++]; // stable sort
		else tmp[i] = arr[ridx++];
	}
	for (int i = st; i < en; ++i)
		arr[i] = tmp[i];
}

// arr[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en) {
	if (en == st + 1) return; // 길이 1인 경우
	int mid = (st + en) / 2;
	merge_sort(st, mid); // arr[st:mid]을 정렬한다.
	merge_sort(mid, en); // arr[mid:en]을 정렬한다.
	merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	merge_sort(0, n);
	for (int i = 0; i < n; i++) cout << arr[i] << ' ';  // -53 3 12 15 16 22 23 25 46 357

	return 0;
}

 

하나의 배열을 두개로 쪼개서 각 배열의 크기가 1이 될때까지 재귀를 호출한다.

실제로 배열 2개를 사용하는것은 아니고 인덱스를 2개를 사용함으로써 쪼갠것과 마찬가지의 작업을 한다.

 

퀵 정렬 (Quick Sort)

 

평균적으로 O(NlogN)의 속도를 내지만 최악의 경우 O(N²)이다.

pivot을 기준으로 바로 값의 교환이 이루어지기 때문에 공간 복잡도는 O(1)이다.

평균적인 속도가 나올때는 병합 정렬보다는 빠르다. 하지만 라이브러리 사용이 불가능한 코딩 테스트를 치룰때는 언제나 최악의 상황을 상정해야 하므로 퀵 정렬보다는 병합 정렬 또는 힙 정렬을 이용해야 한다.

 

함수 호출시 인자에 n-1을 주는경우

 

#include <iostream>
#include <algorithm>

using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en)
{
	if (st >= en) return;

	int pivot = st;
	int left = st + 1;
	int right = en;

	while (left <= right)
	{
		while (left <= en && arr[left] <= arr[pivot]) left++;
		while (right > st && arr[right] >= arr[pivot]) right--;

		if (left > right) swap(arr[pivot], arr[right]);
		else swap(arr[left], arr[right]);
	}
	quick_sort(st, right - 1);
	quick_sort(right + 1, en);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	quick_sort(0, n-1);
	for (int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357

	return 0;
}

 

 

함수 내에서 en을 1 빼는경우

 

#include <iostream>
#include <algorithm>

using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en)
{
	if (st >= en - 1) return;

	int pivot = st;
	int left = st + 1;
	int right = en - 1;

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

		if (left > right) swap(arr[pivot], arr[right]);
		else swap(arr[left], arr[right]);
	}
	quick_sort(st, right - 1);
	quick_sort(right + 1, en);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	quick_sort(0, n);
	for (int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357

	return 0;
}

 

번외 : Stable Sort

 

우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬

예를들어 38, 21, 21, 21이 있다면 수가 같을 때 리스트 앞쪽의 수를 먼저 골라서 정렬한다.

병합 정렬은 Stable Sort이고 퀵 정렬은 Unstable Sort이다.