0x0E,0F - 정렬

# Merge sort

재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법

우선 순위가 같은 원소들끼리 원래 순서가 유지되는 stable sort

 

#include <bits/stdc++.h>
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 idxL = st, idxR = mid;
	for (int i = st; i < en; i++)
	{
		if (idxR == en) tmp[i] = arr[idxL++];
		else if (idxL == mid) tmp[i] = arr[idxR++];
		else if (arr[idxL] <= arr[idxR]) tmp[i] = arr[idxL++];
		else tmp[i] = arr[idxR++];
	}
	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(void) {
	ios::sync_with_stdio(0);
	cin.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
}

 

 

# Quick sort

merge sort vs quick sort

pivot을 기준으로 양쪽이 나뉘고 양쪽에서 따로 따로 pivot을 제자리로 보내는 것을 반복하는 정렬

평균 O(NlgN)이지만 최악의 경우 O(N^2)

 

STL이 없을 때 정렬을 직접 짜야 한다면 merge sort를 쓰는 것이 낫다

또는 최악의 경우에도 O(NlgN)이 보장되는 heap sort로 정렬한다

 

merge sort와 달리 unstable sort

#include <bits/stdc++.h>
using namespace std;

int n = 10;
int arr[1111];
// arr[st ~ en-1] 정렬
void qSort(int st, int en)
{
	if (en <= st + 1) return;	// base condition = 수열의 길이가 1 이하면 종료
	int pivot = arr[st];
	int l = st + 1;
	int r = en - 1;
	while (true)
	{
		while (l <= r and arr[l] <= pivot) l++;
		while (r <= l and arr[r] >= pivot) r--;
		if (l < r) break;	// l과 r이 역전되는 순간 탈출
		swap(arr[l], arr[r]);
	}
	swap(arr[st], arr[r]);	// 역전된 후 pivot을 스왑해주면 pivot이 제자리로 간다
	qSort(st, r);
	qSort(r + 1, en);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	qSort(0, n);
	for (int i = 0; i < n; i++) cout << arr[i] << ' ';
}

 

 

---

# 출처

https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98