Timsort

Timsort(삽입정렬 + 병합정렬)

1. '실제 데이터는 대부분 이미 정렬돼 있을 것이다' 라는 가정에 기반한 정렬 알고리즘.
2. 삽입정렬과 병합정렬을 적절히 조합한 알고리즘.
3. 현업에서 병합정렬, 퀵정렬 보다 더 널리 쓰이는 정렬알고리즘이다.
4. Python, Java SE 7, Android, Google chrome (V8), 그리고 swift까지 많은 프로그래밍 언어에서 표준 정렬 알고리즘으로 채택되어 사용되고 있다.

아이디어

1. 현실세계의 데이터들은 완전 무작위로 배열돼 있기 보단 어느 정도 정렬된 상태로 배열돼 있는 경우가 많지 않을까? (예컨대 옷걸이에 대충 사이즈별로 걸린 옷들처럼)

2. 그렇다면 정렬을 해야하는 전체 배열을 작은 덩어리들로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 Merge sort로 병합하면 좀 더 빠르지 않을까?

간단하게 Insertion sort, merge sort 알아보기

• Insertion sort (삽입 정렬) : 매우 간단하고 직관적인 정렬 알고리즘
  • 배열의 요소들을 앞에서부터 하나씩 확인하며 자신의 위치를 찾아 삽입하는 방식
• Merge Sort (병합 정렬) : 배열을 반으로 나누고 각각을 정렬한 뒤, 다시 병합하는 방식으로 동작합니다.
  • 배열을 절반으로 나누고 각각의 하위 배열에 대해 다시 병합 정렬을 재귀적으로 호출 후 더 이상 나눌 수 없을 때 두 하위 배열을 정렬된 상태로 병합합니다.

Timsort 장점

• 안정적인 두 정렬 방법을 결합했기에 안정적
• 병합 정렬보다 적은 메모리사용 가능
  • 병합 정렬 -> 새로운 배열을 만들어서 사용
  • 팀소트 -> 기존 배열을 효율적으로 병합함
    • [1, 3, 5, 7, 2, 4, 6, 8] ⇒ [1, 3, 5 , 7] 복사 후 [2, 4, 6, 8] 비교 후 기존 배열이 덮어쓰기

시간 복잡도

• 최선의 시간 복잡도 : O(n)
• 평균 시간 복잡도 : O(n log n)
• 최악의 시간 복잡도 : O(n log n)

Timsort의 동작 원리

1. Run(작은 덩어리)을 만든다 : 병합정렬처럼 배열을 계속 만듭니다.
2. 작은 배열 정렬할 때 삽입 정렬을 통해 데이터를 정렬합니다.

최적화

• 병합 정렬에서 발생하는 추가적인 병합 단계를 줄이는 방식으로 최적화 합니다
  • 이미 정렬된 부분을 찾아내어 활용함으로써 정렬 속도를 향상시킵니다.
• 가변 크기의 run을 사용하여 메모리 사용을 최적화합니다.
  • 고정된 크기 대신 데이터의 정렬 상태에 맞춰 덩어리를 나누고, 그 덩어리들을 효율적으로 병합합니다.
  • 병합 하기전 두개의 run 중 크기가 더 작은 run인 배열을 선택하여 복사한다
    • 두 run 중 크기가 작은 run을 담을 메모리가 필요하기에 병합을 진행할 때 최악의 경우 n/2의 추가 메모리를 사용한다. 하지만 Merge sort의 경우 n개의 추가 메모리를 사용하기 때문에 절반을 절약할 수 있다.
• 병합하기 전 병합을 수행할 필요가 없는 구간을 먼저 계산한다

  [3, 5, 11], [9 , 14, 15]
  정렬 안해도 되는 구간 = [3, 5], [14, 15]

• 질주모드
  • 하나의 요소가 한 run을 계속해서 참조할 경우 1, 2, 4, 8… 과 같이 요소를 건너 뛰면서 대소 비교를 진행한다.

덩어리를 쪼개는 방법

예시: 배열 [3, 5, 7, 10, 8, 4, 2, 1]

Timsort는 이미 정렬된 구간 [3, 5, 7, 10]을 하나의 덩어리(run)로 취급하고, 정렬되지 않은 구간을 따로 정렬한 후 병합할 때 사용합니다.
즉, 이미 정렬된 부분은 다시 정렬하지 않고 그대로 유지합니다.

삽입 정렬을 쓰는 이유

• 삽입 정렬은 작은 데이터에서 매우 빠릅니다.
  • 데이터의 양이 적을 때, 요소를 비교하고 이동시키는 작업이 적기 때문입니다.
• 데이터가 정렬되어 있거나 거의 정렬된 상태일 때, 효율적으로 정렬할 수 있습니다.
  • 배열이 이미 완전히 정렬된 경우, 각 요소는 자신의 위치에 이미 있기 때문에 요소들을 단순히 한 번씩 확인하고 지나가면 됩니다. 즉, 불필요한 요소 이동이 전혀 발생하지 않습니다.
  • 데이터가 거의 정렬된 상태일 경우, 소수의 요소들만 위치만 바꾸면 되기 때문에 삽입 정렬은 빠르게 그 위치를 찾아 적절히 삽입합니다. 이 경우, 요소를 많이 이동시키지 않아도 되므로 연산 횟수가 줄어듭니다.

출처

네이버 기술 블로그