개요
본문에서는 파이썬의 sort() 및 sorted() 함수에 적용된 TimSort 알고리즘에 대해 설명하고자 합니다. TimSort는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)의 특성을 결합하여 구현된 고도로 효율적인 정렬 알고리즘입니다. 이 글에서는 TimSort의 작동 원리와 그 구성 방식에 대해 간략히 소개하겠습니다.
Binary insertion sort
특징
- 안정 정렬
- 비교 횟수가 Insertion sort에 비해 적음
Insertion sort 는 비교하는 연산에 최대 O(N^2) 시간이 소요됩니다. 반면 Binary insertion sort는 이러한 비교 연산 O(NlogN) 으로 줄일 수 있는데 어떻게 줄일 수 있는지 insertion sort의 특징과 함께 알아보겠습니다.
Insertion sort code
오름차순 정렬일 경우 Insertion sort는 기준이 되는 인덱스를 잡은뒤에 본인보다 큰수가 이전에 있으면 해당 수를 뒤로 한칸 씩 밀어줍니다. 코드는 아래와 같습니다.
void insertion_sort(vector<int> &vec) {
for (int i = 1; i < vec.size(); i++) {
int key = vec[i];
int j = i - 1;
while (j >= 0 && key < vec[j]) {
vec[j + 1] = vec[j];
j--;
}
vec[j] = key;
}
}
이러한 특징 덕분에 인덱스를 선택할 때 특정 인덱스에서 왼쪽 블록은 정렬되어있다는 것이 보장됩니다.. 즉 왼쪽 블록 원소에서 upper_bound를 통해 본인보다 큰수가 나오는 가장 첫번째 위치를 O(logN) 에 찾을 수 있습니다.
Binary insertion sort
void binary_insertion_sort(vector<int> &vec) {
for (int i = 1; i < vec.size(); i++) {
int small_pos = upper_bound(vec, i);
int k = vec[i];
if (small_pos == -1) continue;
// 본인보다 큰 숫자가 존재하는 구간을 옆으로 한칸 shift 한다. 블록 이동
move(vec.begin() + small_pos, vec.begin() + i, vec.begin() + small_pos + 1);
vec[small_pos] = k;
}
}
Binary insertion sort 는 삽입할 위치를 log(N) 에 찾습니다. 하지만 교환에는 여전이 N이걸리는데 N의 숫자가 작아질수록 O(Nlog(N)) 에 근사한 시간 복잡도를 얻을 수 있습니다.
언제 사용하는가
비교 연산의 시간이 원소 교환의 시간보다 오래 소요되는 곳에서 사용되면 효과적일 수 있습니다. 하지만 여전히 최악의 시간복잡도는 O(N^2) 이다. 이러한 이유로 대부분의 상황에서는 사용되지 않습니다.
Tim Sort 알고리즘
Tim Sort 는 현실 세계의 데이터는 어느정도 정렬되어있다는 것을 가정하고 설계된 알고리즘 입니다. 삽입 정렬과 병합정렬을 조합하여 평균 시간복잡도와 최선 시간복잡도를 개선합니다.
동작원리
TimSort는 파이썬의 기본 정렬 알고리즘으로 널리 알려진 안정적인 정렬 알고리즘입니다. 이 알고리즘은 삽입 정렬과 병합 정렬의 장점을 결합하여 작은 배열에 대해서는 삽입 정렬의 빠른 속도를, 큰 배열에 대해서는 병합 정렬의 효율적인 분할 정복 전략을 사용합니다.
TimSort는 배열을 작은 조각으로 나누고 각 조각을 삽입 정렬로 정렬한 다음, 정렬된 조각들을 병합하면서 전체 배열을 정렬합니다.
TimSort를 C++로 구현하려면 몇 가지 주요 구성 요소를 구현해야 합니다
- 최소 실행 크기 결정: 배열을 최소 크기의 '런(run)'으로 분할합니다. 런의 크기는 일반적으로 32에서 64 사이입니다. 이는 삽입 정렬이 작은 배열에서 효율적이기 때문입니다.
- 삽입 정렬: 각 런을 정렬하기 위해 사용됩니다.
- 병합: 정렬된 런들을 병합하여 최종적으로 전체 배열을 정렬합니다.
구현
int upper_bound(vector<int> &vec, int pos) {
int s = 0, e = pos - 1;
while (s < e) {
int m = (s + e) / 2;
if (vec[m] <= vec[pos]) s = m + 1;
else e = m;
}
// 큰 원소를 찾지 못했을 경우
if (vec[s] <= vec[pos]) return -1;
return s;
}
const size_t RUN = 32;
void binary_insertion_sort(vector<int> &vec, int left, int right) {
for (int i = left+1; i <= right; i++) {
int small_pos = upper_bound(vec, i);
int k = vec[i];
if (small_pos == -1) continue;
// 본인보다 큰 숫자가 존재하는 구간을 옆으로 한칸 shift 한다. 블록 이동
move(vec.begin() + small_pos, vec.begin() + i, vec.begin() + small_pos + 1);
vec[small_pos] = k;
}
}
void merge(vector<int> &vec, int l, int m, int r) {
int len1 = m - l + 1, len2 = r - m;
int left[len1], right[len2];
for (int i = 0; i < len1; i++)
left[i] = vec[l + i];
for (int i = 0; i < len2; i++)
right[i] = vec[m + 1 + i];
int i = 0;
int j = 0;
int k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) {
vec[k] = left[i];
i++;
} else {
vec[k] = right[j];
j++;
}
k++;
}
while (i < len1) {
vec[k] = left[i];
k++;
i++;
}
while (j < len2) {
vec[k] = right[j];
k++;
j++;
}
}
void timSort(vector<int> &vec, int n) {
for (int i = 0; i < n; i += RUN)
binary_insertion_sort(vec, i, min((i + 31), (n - 1)));
for (int size = RUN; size < n; size = 2 * size) {
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size - 1;
int right = min((left + 2 * size - 1), (n - 1));
if (mid < right)
merge(vec, left, mid, right);
}
}
}
int main() {
vector<int> vec = {1, 4, 5, -2, -3, 5, 10};
timSort(vec, (int)vec.size());
for(int i: vec) cout << i << " ";
return 0;
}
'알고리즘 > 이론' 카테고리의 다른 글
[알고리즘] - UnionFind (0) | 2024.02.05 |
---|