Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 팀 정렬(Timsort) 알고리즘 완벽 가이드

팀 정렬(Timsort)이란?

팀 정렬(Timsort)은 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 아이디어를 결합한 안정적(stable)인 정렬 알고리즘입니다. 두 알고리즘의 장점을 살린 하이브리드 정렬이라고도 부르며, Java와 Python의 내장 정렬 함수에 실제로 채택되어 있을 만큼 검증된 방식입니다.

핵심 아이디어는 간단합니다. 배열을 작은 단위로 나누어 삽입 정렬로 각 조각을 빠르게 정렬한 뒤, 병합 정렬의 merge 함수를 이용해 정렬된 조각들을 하나로 합치는 것입니다.

동작 원리

팀 정렬에서는 배열을 작은 덩어리(chunk)로 나누는데, 이 덩어리를 RUN이라고 부릅니다. 전체 과정은 다음과 같습니다.

  • 배열을 RUN 크기의 조각으로 분할합니다.
  • 각 RUN을 삽입 정렬 기법으로 정렬합니다.
  • 모든 RUN이 정렬되면 병합(merge) 함수를 사용해 하나의 정렬된 배열로 합칩니다.

배열의 크기가 RUN보다 작은 경우에는 배열 전체를 삽입 정렬로 바로 정렬하면 됩니다. 일반적으로 RUN 크기는 배열 크기에 따라 32~64 사이의 값으로 설정하며, 병합 함수는 서브 배열의 크기가 2의 거듭제곱일 때만 수행됩니다.

삽입 정렬을 활용하는 이유는, 삽입 정렬이 크기가 작은 배열에서 매우 효율적으로 동작하기 때문입니다. 반대로 큰 배열 전체를 병합하는 데에는 병합 정렬의 O(n log n) 성능을 활용합니다.

시간 복잡도

  • 최선의 경우(Best case): Ω(n)
  • 평균 경우(Average case): O(n log n)
  • 최악의 경우(Worst case): O(n log n)

팀 정렬 알고리즘의 단계

  1. 크기가 32인 RUN을 초기화합니다.
  2. RUN 크기만큼의 조각에 대해 삽입 정렬을 수행합니다.
  3. 배열, 왼쪽 인덱스, 중간 인덱스, 오른쪽 인덱스를 입력받는 merge(int arr[], int l, int m, int r) 함수를 정의합니다. 이 함수는 크기 32의 정렬된 청크들을 병합하여 반환합니다.
  4. 왼쪽 요소들을 담는 배열과 오른쪽 요소들을 담는 배열의 길이를 초기화합니다.
  5. 왼쪽 배열과 오른쪽 배열을 채운 후, 두 배열을 순회(iterate)합니다.
  6. 왼쪽 배열의 요소가 오른쪽 배열의 요소보다 작으면, 그 요소를 결과 배열(더 큰 배열)에 넣습니다.
  7. 그렇지 않으면 오른쪽 배열의 요소를 결과 배열에 넣습니다.
  8. 순회가 끝난 후 왼쪽 배열과 오른쪽 배열에 남아 있는 요소들을 결과 배열에 모두 복사합니다.
  9. 배열과 그 크기를 입력받는 timSortAlgo(int arr[], int n) 함수를 정의합니다. 이 함수는 먼저 삽입 정렬을 호출하고, 이후 배열 요소들을 병합합니다.
  10. 팀 정렬을 통해 최종 정렬된 배열을 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // 청크를 나누기 위한 RUN 초기화

// RUN 크기의 청크에 대해 삽입 정렬 수행
void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++){
        int t = arr[i];
        int j = i - 1;
        while (j >= left && t < arr[j]){
            arr[j+1] = arr[j--];
        }
        arr[j+1] = t;
    }
}

// 병합 함수: 크기 32로 정렬된 청크들을 하나로 합침
void merge(int arr[], 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] = arr[l + i];      // 왼쪽 배열 채우기
    for (int i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i]; // 오른쪽 배열 채우기

    int i = 0;
    int j = 0;
    int k = l;

    // 왼쪽 배열과 오른쪽 배열을 동시에 순회
    while (i < len1 && j < len2){
        if (left[i] <= right[j]){ // 왼쪽 요소가 더 작으면 결과 배열에 저장
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];    // 오른쪽 요소가 더 작거나 같으면 저장
            j++;
        }
        k++;
    }

    // 왼쪽 배열에 남은 요소 복사
    while (i < len1){
        arr[k] = left[i];
        k++;
        i++;
    }

    // 오른쪽 배열에 남은 요소 복사
    while (j < len2){
        arr[k] = right[j];
        k++;
        j++;
    }
}

void timSortAlgo(int arr[], int n){
    // 각 RUN 청크에 대해 삽입 정렬 호출
    for (int i = 0; i < n; i+=RUN)
        insertionSort(arr, i, min((i+31), (n-1)));

    // 크기 RUN(32)부터 병합 시작, 2*RUN까지 계속 진행
    for (int s = RUN; s < n; s = 2*s){
        // 왼쪽 서브 배열의 시작 지점 선택
        // arr[left .. left+s-1] 와 arr[left+s .. left+2*s-1] 을 병합
        // 병합이 끝날 때마다 left를 2*s씩 증가
        for (int left = 0; left < n; left += 2*s){
            int mid = min((left + s - 1), (n-1)); // 왼쪽 서브 배열의 끝 지점
            int right = min((left + 2*s - 1), (n-1));
            // 서브 배열 arr[left.....mid] 와 arr[mid+1....right] 를 병합
            merge(arr, left, mid, right);
        }
    }
}

void printArray(int arr[], int n){
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// 팀 정렬 알고리즘을 실행하는 메인 함수
int main(){
    int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "원본 배열: ";
    printArray(arr, n);

    // 배열을 정렬하기 위해 timSortAlgo 함수 호출
    timSortAlgo(arr, n);

    cout << "팀 정렬 적용 후 배열: ";
    printArray(arr, n); // 출력 함수 호출

    return 0;
}