팀 정렬 (Tim Sort)

원하는 기준으로 배열을 재나열하는 정렬 알고리즘

 

 

팀 정렬 (Tim Sort)

팀 정렬은 Java의 객체 배열을 정렬할 때 사용하는 알고리즘 입니다. 팀 정렬은 삽입 정렬과 병합 정렬의 강점을 결합했습니다. 삽입 정렬의 작은 데이터 세트에 대해 효율적인 면과 병합 정렬의 큰 데이터 세트에 효율적인 면을 합친 것입니다. 팀 정렬은 배열을 여러 부분으로 나눕니다. 이렇게 나누어진 부분을 run이라고 하며 각 run에서는 삽입 정렬로 정렬합니다. 정렬된 run들은 병합 정렬로 합치면서 정렬합니다. 이런 식으로 작은 부분에는 삽입 정렬을 큰 부분에서는 병합 정렬을 이용해 각 정렬들의 강점을 활용하여 정렬합니다. 

 

시간 복잡도 

평균 경우 : O(n log n)

최악 경우 : O(n log n) 

 

평균, 최악 모두 O(n log n)으로 일정한 성능을 보입니다. 또한 이미 정렬된 데이터 세트에 대해 더 빠른 속도를 냅니다. 

 

 

객체 배열 특징

• 복잡한 비교 연산 : 객체들은 여러 속성을 기반으로 비교되므로 원시 타입보다 복잡하고 시간이 더 소요됩니다. 
• 큰 메모리 공간 : 객체 배열은 원시 배열보다 더 큰 메모리 공간을 사용합니다. 

 

팀 정렬의 특징 

• 안정성 : 같은 값의 순서가 정렬 후에도 유지됩니다. 
• 적응성 : 이미 정렬된 배열에서 순서를 따르므로 적게 비교하여 빠르게 정렬합니다. 
• 하이브리드 알고리즘 : 삽입 정렬과 병합 정렬의 조합으로 각 정렬의 장점을 활용합니다. 

 

객체 배열은 원시 배열에 비해 여러 속성을 가지고 있어서 정렬 후에도 순서가 유지되는 안정성이 중요합니다. 또한 객체의 다중 속성 비교나 날짜 등 원시 타입에 비해서 비교 연산이 복잡합니다. 팀 정렬은 runs의 병합 과정에서 최소한의 비교와 데이터 이동이 이루어집니다. 이런 특징으로 객체 배열을 정렬할 때 팀 정렬을 활용합니다.

 

 

 

장점

• 안정성 : 동일한 값에 대해 원래 순서를 정렬 후에도 유지합니다.
• 일정한 성능 : 평균, 최악 모든 경우에도 O(n log n) 시간 복잡도를 가집니다.
• 대규모 데이터 처리 : 큰 데이터셋에 대해 이미 정렬된 부분을 활용하여 빠르고 효율적으로 정렬합니다. 

 

단점

• 복잡한 알고리즘 : 구현이 상대적으로 어려울 수 있습니다.
• 추가 메모리 : 병합 과정에서 추가적인 메모리가 필요합니다. 
• 작은 데이터셋 : 매우 작은 데이터셋에서는 다른 간단한 정렬 알고리즘(삽입 정렬)이 효율적일 수 있습니다. 

 

 

TimSort는 이러한 특징으로 Java의 객체 배열 정렬에 활용하고 있습니다. 특히 부분적으로 정렬된 큰 데이터셋에 대해 높은 효율을 보이는 것이 주요한 장점입니다. 

 

 

 

동작 과정

1. 배열 분할 : 배열을 작은 조각(일반적으로 32 ~ 64 길이의 요소)로 분할합니다. 이 작은 조각들을 런(run)이라 부릅니다.

2. 각 런 정렬 : 각 런에 대해 삽입 정렬로 정렬합니다. 삽입 정렬은 작은 데이터셋에 대해 효율적이기 때문입니다.

3. 런 병합 : 정렬된 런들을 병합 정렬을 사용하여 합쳐 전체 배열 정렬을 완성합니다.

 

 

 

 

예시

 

예시 배열 

[3,1,5,9,4,8,7,10,13,15,17,20,30,25]

 

 

분할

배열을 작은 조각으로 나눕니다. 여기서는 4의 길이의 run들로 분할하겠습니다. 

[3, 1, 5, 9], [4, 8, 7, 10], [13, 15, 17, 20], [30, 25]

 

 

run 정렬 

분할된 run들을 삽칩 정렬을 통해 정렬합니다. 

[1, 3, 5, 9], [4, 7, 8, 10], [13, 15, 17, 20], [25, 30]

 

 

병합

정렬된 run들을 병합하여 전체 배열을 완성합니다. 

[1, 3, 4, 5, 7, 8, 9, 10, 13, 15, 17, 20, 25, 30]

 

 

 

 

Java 구현 코드

/*
팀소트
시간복잡도 : O(n log n)
삽입 정렬과 병합 정렬의 장점을 합친 정렬
배열을 수많은 요소들로 나눈다(32 ~ 64 등등)
이 요소들은 런이라 불리면 각 런에 대해 삽입 정렬을 통해 정렬한다.
정렬된 런들을 합하여 전체 배열의 정렬을 완성한다.

작은 런들에서 효율적인 삽입 정렬의 이점을 보고 큰 배열에서는 효율적인 병합 정렬의 이점을 모두 활용한다.
 */
public class TimSort {


  // 런의 크기 설정
  private static final int RUN = 32;

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7,10,13,15,17,20,30,25};
    printArray(array);
    long start = System.currentTimeMillis();
    timSort(array);
    long end = System.currentTimeMillis();
    printArray(array);
    System.out.println(start + " " + end);
  }

  public static void timSort(int[] array) {
    int n = array.length;

    // 런 크기에 따라 배열을 여러 부분으로 나누고 각 부분에 대해 삽입 정렬 수행한다.
    for(int i = 0; i < n; i += RUN) {
      insertionSort(array, i, Math.min( (i + RUN - 1), n-1 ));
    }

    // 런들을 병합
    // RUN이 2라면 처음에는 크기가 2인 런들을 병합한다.
    // 그 이후 4, 8, 16인 런들을 병합한다.
    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(array, left, mid, right);
        }
      }
    }
  }

  // 삽입 정렬
  public static void insertionSort(int[] array, int left, int right) {
    for(int i = left + 1; i <= right; i++) {

      // 탐색하는 값이 앞의 값보다 작으면 위치를 바꿈
      // 즉, 앞의 값이 작을 때까지 계속 앞으로 보내서 정렬시킴
      int temp = array[i];
      int j = i - 1;
      
      while(j >= left && array[j] > temp) {
        array[j + 1] = array[j];
        j--;
      }
      array[j+1] = temp;
    }
  }

  // 배열의 두 부분을 병합하는 메소드
  public static void merge(int[] array, 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(array, l, left, 0, len1);
    System.arraycopy(array, m+1, right, 0, len2);

    // 병합 과정
    int i = 0; // left 인덱스
    int j = 0; // right 인덱스
    int k = l; // 병합 될 배열의 인덱스

    while(i < len1 && j < len2) {
      if(left[i] <= right[j]) {
        array[k++] = left[i++];
      }
      else {
        array[k++] = right[j++];
      }
    }

    // 남은 요소 복사
    while(i < len1) {
      array[k++] = left[i++];
    }
    while(j < len2) {
      array[k++] = right[j++];
    }

  }

  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }
}

 

 

 

 

마무리

Java의 객체 정렬 알고리즘인 Timsort를 정리했습니다.

감사합니다.