인트로 정렬 Introsort
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
인트로 정렬은 평균적으로 빠른 성능을 내면서 최악의 조건에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다.
퀵 정렬로 시작한 다음 재귀 깊이가 정렬 대상 요소의 수의 레벨(로그)을 초과할 때 힙 정렬로 전환하며 요소의 수가 특정 임계치 미만일 때 삽입 정렬로 전환한다.
3가지 알고리즘의 좋은 부분을 합쳐놓은 것이며 인트로 정렬이 사용하는 이 3가지 알고리즘은 비교 정렬이기 때문에 인트로 정렬 또한 비교 정렬이다.
| 알고리즘 | 최선 (Best) | 평균 (Average) | 최악 (Worst) |
|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n^2) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) |
우리가 자주 사용하는 C++ STL의 std::sort는 인트로 정렬을 사용한다.
퀵 정렬은 평균적으로 매우 빠르지만 피벗을 잘못 선택했을 때 치명적이다. 이미 정렬된 데이터나 역순 데이터에서 가장 끝값을 피벗으로 잡으면, 분할이 1개와 n - 1개로 이루어지는 불균형이 발생한다. 이 경우 재귀 호출이 n번 발생하고 시간 복잡도도 O(n^2)이 된다.
인트로 정렬은 재귀의 깊이가 log n을 초과하면 힙 정렬로 전환하여 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다.
그리고 배열의 크기가 작을 때는 삽입 정렬이 퀵 정렬보다 빠르기 때문에, 작은 배열에서는 삽입 정렬로 전환하여 성능을 최적화한다. 퀵 정렬이나 힙 정렬은 재귀 호출, 스택 메모리 사용 등 기본적으로 오버헤드가 있지만, 삽입 정렬은 간단한 반복문으로 구현할 수 있고 바로 옆에 있는 메모리들을 순차적으로 접근하기 때문에 캐시 효율이 좋다.
이렇게 세 가지 알고리즘의 장점을 조합하여, 인트로 정렬은 좋은 성능을 제공한다.
간단한 의사 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
void intro_sort_concept(std::vector<int>& arr, int depth_limit)
{
int n = arr.size();
// 1. 데이터가 적으면 삽입 정렬 수행
if (n < 16)
{
// std::insertion_sort(arr.begin(), arr.end());
return;
}
// 2. 재귀 깊이가 한계를 넘으면 힙 정렬로 전환 (안전장치)
if (depth_limit == 0)
{
std::make_heap(arr.begin(), arr.end());
std::sort_heap(arr.begin(), arr.end());
return;
}
// 3. 기본은 퀵 정렬 진행
// partition logic...
// intro_sort_concept(left_part, depth_limit - 1);
// intro_sort_concept(right_part, depth_limit - 1);
}
int main()
{
std::vector<int> data = { /* 아주 많은 데이터 */ };
int limit = std::floor(std::log2(data.size())) * 2;
intro_sort_concept(data, limit);
return 0;
}
참고