팀 정렬(Tim Sort)

팀 정렬(Tim Sort)은 2002년 팀 피터스(Tim Peters)가 개발한 정렬 알고리즘으로, 파이썬의 기본 정렬 알고리즘으로 채택되었습니다. 팀 정렬은 합병 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 장점을 결합한 하이브리드 알고리즘으로, 실제 데이터에서 매우 효율적입니다. 팀 정렬은 분할 정복 기법을 사용하며, 데이터의 부분 정렬(run)을 찾고 이를 병합하여 정렬을 완료합니다.

예시를 통해 팀 정렬 설명하기

1. 주어진 배열:

[5, 21, 7, 23, 19, 10, 17, 15, 1, 3, 2, 11, 6, 12, 14, 4, 13, 9, 8, 16, 18, 20]

2. 작은 배열 정렬 (삽입 정렬):

먼저 작은 크기의 배열을 정렬합니다. 일반적으로 팀 정렬에서는 RUN 크기(보통 32 또는 64)로 배열을 나누고, 각 부분 배열을 삽입 정렬로 정렬합니다.

예를 들어 RUN = 8 인 경우, 부분 배열을 다음과 같이 나눕니다:

[5, 21, 7, 23, 19, 10, 17, 15]
[1, 3, 2, 11, 6, 12, 14, 4]
[13, 9, 8, 16, 18, 20]

각 부분 배열을 삽입 정렬로 정렬합니다:

[5, 7, 10, 15, 17, 19, 21, 23]
[1, 2, 3, 4, 6, 11, 12, 14]
[8, 9, 13, 16, 18, 20]

3. 병합 단계:

작은 배열들을 순차적으로 병합합니다. 이 과정은 병합 정렬의 병합 과정과 유사합니다.

첫 번째 병합 단계:

병합 [5, 7, 10, 15, 17, 19, 21, 23] 와 [1, 2, 3, 4, 6, 11, 12, 14]:
[1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 14, 15, 17, 19, 21, 23]

두 번째 병합 단계:

병합 [1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 14, 15, 17, 19, 21, 23] 와 [8, 9, 13, 16, 18, 20]:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23]

결과:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23]

import java.util.Arrays;

public 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, 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, j = 0, 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++;
        }
    }

    public static void timSort(int[] arr, int n) {
        for (int i = 0; i < n; i += RUN) {
            insertionSort(arr, i, Math.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 = Math.min((left + 2 * size - 1), (n - 1));

                if (mid < right) {
                    merge(arr, left, mid, right);
                }
            }
        }
    }

    public static void printArray(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 21, 7, 23, 19, 10, 17, 15, 1, 3, 2, 11, 6, 12, 14, 4, 13, 9, 8, 16, 18, 20};
        int n = arr.length;
        System.out.println("Given Array is");
        printArray(arr, n);

        timSort(arr, n);

        System.out.println("After Sorting Array is");
        printArray(arr, n);
    }
}