초보 자바 프로그래밍(25) - 팀정렬 (Tim Sort)

팀 정렬 대표 이미지

🔖 INDEX

 

 

팀 정렬(Tim Sort)은 파이썬에서 기본 정렬 알고리즘으로 사용되는 안정적인 비교 기반 정렬 알고리즘입니다. 팀 정렬은 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 아이디어를 결합한 하이브리드 알고리즘으로, 실제 데이터의 특성을 고려해 높은 성능을 발휘합니다.

 

팀 정렬의 작동 원리

팀 정렬의 작동 원리는 다음과 같습니다: ​

1. 배열을 연속된 작은 부분 배열(subarrays)로 분할합니다. 이 부분 배열들은 이미 정렬되어 있거나 거의 정렬된 상태일 수 있습니다. 이러한 부분 배열을 '런(run)'이라고 합니다.
2. 삽입 정렬을 사용하여 각 런을 정렬합니다. 작은 크기의 런에서는 삽입 정렬이 상대적으로 빠른 속도를 보입니다.
3. 병합 정렬의 병합 과정을 사용하여 인접한 런들을 결합합니다. 이 과정은 모든 런이 하나의 정렬된 배열이 될 때까지 반복됩니다.

 

팀 정렬의 특징

팀 정렬의 특징은 다음과 같습니다: ​

1. 안정적인 정렬(Stable Sort): 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 유지됩니다.
2. 적응 정렬(Adaptive Sort): 입력 데이터의 특성에 따라 알고리즘의 동작이 변경되어 성능이 개선됩니다. 예를 들어, 이미 정렬된 부분이 많은 경우 더 빠른 속도를 보입니다.
3. 시간 복잡도(Time Complexity): 최선과 평균의 경우 O(n log n)의 시간 복잡도를 가지며, 최악의 경우에도 O(n log n)의 시간 복잡도를 유지합니다. ​

 

 

팀 정렬의 장점

• 안정성: 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 유지되어 안정성이 요구되는 경우에 적합합니다.
• 적응성: 입력 데이터의 특성을 고려해 성능이 개선되는 특성을 가지고 있습니다. 실제 데이터의 특성에 따라 높은 성능을 발휘합니다.
• 일관된 성능: 최악의 경우에도 O(n log n)의 시간 복잡도를 유지하므로, 일관된 성능이 요구되는 경우에 적합합니다. ​

 

팀 정렬의 단점

• 메모리 사용량: 병합 정렬과 같이 팀 정렬은 추가적인 메모리를 사용합니다. 이로 인해 메모리 제약이 있는 상황에서는 다른 정렬 알고리즘을 고려해야 할 수 있습니다. ​

 

팀 정렬의 구현 예제

팀 정렬은 자바에서 다음과 같이 구현할 수 있습니다. 이는 병합 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘입니다. 

import java.util.Arrays;

class TimSort {
    private static final int RUN = 32; // 작은 구간의 크기를 정의

    // 삽입 정렬 함수
    public static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    // 두 정렬된 배열을 병합하는 함수
    public static void merge(int[] arr, int l, int m, int r) {
        int len1 = m - l + 1;
        int len2 = r - m;
        int[] left = new int[len1];
        int[] right = new int[len2];
        System.arraycopy(arr, l, left, 0, len1);
        System.arraycopy(arr, m + 1, right, 0, len2);

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

    // TimSort 알고리즘을 수행하는 함수
    public static void timSort(int[] arr, int n) {
        // 배열을 RUN 크기의 작은 구간으로 나누어 삽입 정렬 수행
        for (int i = 0; i < n; i += RUN) {
            insertionSort(arr, i, Math.min(i + RUN - 1, 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 = Math.min(left + 2 * size - 1, n - 1);

                merge(arr, left, mid, right);
            }
        }
    }

    // 메인 함수
    public static void main(String[] args) {
        int[] arr = {5, 21, 7, 23, 19, 50, 29, 14, 1, 31};
        int n = arr.length;
        System.out.println("Original Array:");
        System.out.println(Arrays.toString(arr));

        timSort(arr, n);

        System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(arr));
    }
}

 

 

위 코드에서는 팀 정렬을 구현하기 위해 삽입 정렬(insertionSort)과 병합 정렬의 병합 부분(merge)을 사용했습니다. 배열을 작은 블록(RUN)으로 나누어 삽입 정렬을 수행한 후, 병합 정렬의 병합 과정을 통해 정렬을 완료합니다. 이러한 방식으로 팀 정렬은 이미 정렬되어 있는 부분에 대해 빠른 속도를 보이며 전체적으로 효율적인 정렬을 수행합니다. ​

 

주요 구성 요소는 다음과 같습니다. ​

• RUN: 정렬되지 않은 배열을 작은 블록(RUN)으로 나누어 삽입 정렬을 수행하는데 사용됩니다. 이 값은 튜닝 가능한 상수로, 일반적으로 32 또는 64를 사용합니다.
• insertionSort(): 주어진 범위 내에서 삽입 정렬을 수행하는 함수입니다. 이 함수는 각 RUN에 대해 호출되며, 작은 범위에서의 정렬을 빠르게 수행합니다.
• merge(): 병합 정렬의 병합 과정을 수행하는 함수입니다. 삽입 정렬로 정렬된 RUN들을 병합하여 전체 배열을 정렬합니다.
• timSort(): 팀 정렬의 전체 과정을 수행하는 함수입니다. 배열을 RUN 단위로 나누어 삽입 정렬을 수행한 후, 병합 과정을 반복하여 정렬을 완료합니다. ​

팀 정렬은 실제 데이터의 특성을 고려하여 성능을 개선하는 적응 정렬 알고리즘입니다. 따라서 입력 데이터의 특성에 따라 알고리즘의 성능이 크게 달라질 수 있습니다. 실제 데이터의 특성을 이해하고 적절한 정렬 알고리즘을 선택하는 것이 중요합니다. ​

 

또한 팀 정렬은 병합 정렬과 삽입 정렬의 아이디어를 결합한 하이브리드 알고리즘으로, 이러한 두 알고리즘의 구현에도 영향을 받습니다. 효율적인 병합 및 삽입 정렬 구현을 사용하여 전체적인 팀 정렬의 성능을 향상시킬 수 있습니다.