Merge Sort
분할정복을 기반으로 하는 정렬 방식으로, 수열을 분할하고 합칠 때에 정렬하여 합친다.
분할
인덱스의 중간값을 기준으로 절반으로 나누어 하나의 원소가 될 때까지 재귀적으로 분할한다.
크기가 N인 배열을 분할하는 경우의 시간복잡도는 O(N) 이다.
합병
두 수열을 정렬하여 합쳐야 한다. 하나의 원소부터 정렬해나가므로 두 수열은 이미 정렬되어 있는 것이다.
따라서 정렬되어 있는 두 수열을 정렬하여 합치면 된다.
정렬되어 있는 두 배열 합치기
11728번: 배열 합치기 문제로 연습해볼 수 있다.
크기가 A인 배열과 크기가 B인 두 배열을 정렬하여 하나로 합치는 경우의 시간복잡도는 O(A+B)이다.
즉, 합친 크기가 N인 배열로 합병하는 경우의 시간복잡도는 O(N)이라는 것을 알 수 있다.
다시 MergeSort의 합병 과정으로 돌아오면,
두 수열의 맨 앞의 원소부터 비교하여 임의의 배열 tmp에 작은 원소부터 삽입하고 해당 배열의 값을 기존 배열의 값으로 바꾸어준다. 여기서 공간이 O(N) 만큼 필요하게 된다.
또한, 배열 합치기 문제를 통해서 알아본 바와 같이 크기가 N인 배열로 합치는데에 필요한 시간은 O(N)이다.
절반씩 나누어 진행하기 때문에 N개의 원소를 가진 트리의 높이는 logN이므로 합병하는 경우의 시간복잡도는 N * logN = O(NlogN) 이다.
시간복잡도
분할하는 경우의 시간복잡도는 O(N)이고, 합병하는 경우의 시간복잡도는 O(NlogN)이고,
O(N) < O(NlogN) 이므로 Merge Sort에서 최종적인 시간복잡도는 O(NlogN) 이다.
구현
Merge Sort를 구현하여 2751번: 수 정렬하기 2 문제를 푼 코드는 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000001];
int tmp[1000001];
// 두 리스트 병합
void merge(int s, int e) {
int m = (s + e) / 2;
int idx_s = s;
int idx_e = m;
for (int i=s;i<e;i++) {
if (idx_s == m) // 앞 배열이 이미 모두 tmp에 담긴 경우
tmp[i] = arr[idx_e++];
else if (idx_e == e) // 뒤 배열이 이미 모두 tmp에 담긴 경우
tmp[i] = arr[idx_s++];
else if (arr[idx_s] <= arr[idx_e])
tmp[i] = arr[idx_s++];
else
tmp[i] = arr[idx_e++];
}
for (int i=s;i<e;i++)
arr[i] = tmp[i];
}
// 재귀적으로 리스트 분할 -> arr[s:m], arr[m:e]으로 나눈다
void merge_sort(int s, int e) {
if (s + 1 == e)
return;
int m = (s + e) / 2;
merge_sort(s, m);
merge_sort(m, e);
merge(s, e);
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i=0;i<n;i++)
cin >> arr[i];
merge_sort(0, n);
for (int i=0;i<n;i++)
cout << arr[i] << '\n';
return 0;
}
Quick Sort
merge sort와 동일하게 분할정복을 기반으로 하는 정렬이다.
pivot을 설정하여 pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 수를 배치하고, pivot의 오른쪽에는 pivot보다 큰 수를 배치한다. 그리고 pivot을 기준으로 나머지 배열도 쪼개서 재귀적으로 동일한 작업을 수행한다.
시간복잡도
하나의 피벗을 설정하여 정렬을 수행하는 과정은 O(N)시간이 걸린다. 재귀적으로 배열을 쪼개어 수행하므로 쪼개진 트리의 높이인 O(logN)만큼 해당 연산을 수행한다.
따라서 Quick Sort에서 최종적인 시간복잡도는 O(NlogN) 이다.
하지만!
이는 평균적인 경우에서의 시간복잡도이다.
이미 정렬되어 있는 배열에서 맨 앞의 원소를 피벗으로 설정하여 정렬을 진행하게 되면, 트리의 높이 즉, 연산횟수가 O(logN)이 아니라 O(N)이 되어버린다. 이 경우에서의 시간복잡도는 O(N^2)이 된다.
Quick Sort의 평균적인 시간복잡도는 O(NlogN) 이고, 최악의 경우에서의 시간복잡도는 O(N^2) 이다.
최악의 경우를 해결하기 위한 방법
pivot을 랜덤하게 설정하거나, 피벗 후보를 3개 정해서 그 3개 중에서 중앙값을 피벗으로 두는 방식을 사용하기도 한다.
구현
pivot을 맨 앞의 원소로 설정하여 Quick Sort를 구현한 코드는 다음과 같다.
2751번: 수 정렬하기 2 문제에 제출하면, 최악인 경우의 시간복잡도가 O(N^2)이어서 통과하지 못한다.
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000001];
void quick_sort(int s, int e) {
if (s + 1 >= e)
return ;
int pivot = arr[s];
int l = s+1;
int r = e-1;
while (true) {
while (l <= r && arr[l] <= pivot)
l++;
while (l <= r && arr[r] >= pivot)
r--;
if (l > r)
break;
swap(arr[l], arr[r]);
}
swap(arr[s], arr[r]);
quick_sort(s, r);
quick_sort(r+1, e);
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i=0;i<n;i++)
cin >> arr[i];
quick_sort(0, n);
for (int i=0;i<n;i++)
cout << arr[i] << '\n';
return 0;
}
Counting Sort (계수 정렬)
non-comparison sort로 원소들의 값을 서로 비교하는 것이 아니라
숫자가 등장한 횟수를 세서 배열에 저장한 후에 등장한 횟수만큼 순서대로 출력한다.
간단하고 직관적으로 정렬할 수 있지만, 숫자의 범위를 알아야하고 숫자의 범위만큼의 공간이 필요하다.
가능한 숫자의 범위는 크지만 실제로 사용되는 숫자의 범위가 좁은 경우에는 불필요한 순회시간이 사용된다.
메모리 제한이 512MB라고 하면 int 기준으로 약 1.2억보다 작은 범위를 갖는 배열만이 가능한 것이다.
즉, 작은 범위를 갖는 경우에만 counting sort를 사용하는 것이 유리하다.
시간복잡도
배열의 크기가 N이고, 수의 범위가 K인 경우라면
N만큼 배열을 순회하여 횟수를 세고, 범위 전체의 크기 K만큼을 순회하면서 출력하기 때문에
Counting Sort의 시간복잡도는 O(N+K)이다.
구현
수 정렬하기 5 문제 풀이 코드
음수인 원소도 존재해서 인덱스값에 10000000만큼을 더해서 수가 등장한 횟수를 카운트해서 저장해주었다.
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt[20000001];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i=0;i<n;i++) {
int x;
cin >> x;
int idx = x + 10000000;
cnt[idx]++;
}
for (int i=0;i<20000001;i++) {
for (int j=0;j<cnt[i];j++)
cout << i - 10000000 << '\n';
}
return 0;
}Radix Sort (기수 정렬)
Counting Sort와 마찬가지로 non-comparison sort로 원소들의 값을 서로 비교하지 않고 정렬을 한다.
사람이 수를 비교하는 것과 유사하게 각 자리수를 비교하여 정렬한다.
1의 자리부터 10의 자리, 100의 자리를 순서대로 비교하면서 정렬한다.
1의 자리가 0이면 0번째 배열에 해당 수를 넣는다. 모든 수를 순회하면서 1의 자리가 9에 해당하는 수까지 전부 배열에 넣는다.
그 후에 10의 자리에 따라서 동일한 작업을 진행하면, 이전에 1의 자리에 따른 정렬이 상대적으로 유지되므로 모든 수가 정렬된다.
시간복잡도
최대 D개의 자릿수를 갖는 N개의 원소를 정렬하는 경우,
하나의 자릿수마다 모든 원소를 순회하므로 D * N만큼의 연산이 수행된다.
따라서 Radix Sort의 시간복잡도는 O(DN) 이다.
구현
#include <bits/stdc++.h>
using namespace std;
int N;
int p[5]; // 자릿수에 따른 10의 제곱 값
int d = 5; // 자릿수
int arr[10000001];
vector<int> L[10]; //0부터 9까지의 동적배열
// x의 10^a 자리 숫자 반환
int digitNum(int x, int a) {
return (x/ p[a]) % 10;
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
// 거듭제곱 초기화
p[0] = 1;
for (int i=1; i<d; i++)
p[i] = p[i-1] * 10;
// 입력
cin >> N;
for (int i=0; i<N; i++)
cin >> arr[i];
// 자릿수만큼 반복하면서 정렬
for (int i=0; i<d; i++) {
for (int j=0; j<10; j++) // 새로운 자릿수를 넣어주기 위해서 비워주기
L[j].clear();
for (int j=0; j<N; j++) // 새로운 자릿수에 따라 값 갱신
L[digitNum(arr[j], i)].push_back(arr[j]);
int idx = 0;
for (int j=0; j<10; j++) { //갱신한 순서대로 arr 배열에 다시 저장
for (auto x : L[j])
arr[idx++] = x;
}
}
for (int i=0; i<N; i++)
cout << arr[i] << endl;
return 0;
}
ref.
BaaaaaaaarkingDog 실전 알고리즘 0x0E강 - 정렬
BaaaaaaaarkingDog 실전 알고리즘 0x0F강 - 정렬II
