[알고리즘] - Timsort

개요

본문에서는 파이썬의 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++로 구현하려면 몇 가지 주요 구성 요소를 구현해야 합니다

1. 최소 실행 크기 결정: 배열을 최소 크기의 '런(run)'으로 분할합니다. 런의 크기는 일반적으로 32에서 64 사이입니다. 이는 삽입 정렬이 작은 배열에서 효율적이기 때문입니다.
2. 삽입 정렬: 각 런을 정렬하기 위해 사용됩니다.
3. 병합: 정렬된 런들을 병합하여 최종적으로 전체 배열을 정렬합니다.

구현

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;
}