Algorithm - Tim Sort

built-in method sort

• built-in method sort : JavaScript를 해석하는 엔진에서 어떻게 구현했으냐에 따라서 정렬된 알고리즘이 달라짐
  • Chrome의 V8 엔진에서는 정렬 알고리즘으로 Tim Sort를 사용함
  • Firefox의 Spidermoney에서는 정렬 알고리즘으로 Merge Sort를 사용함

Tim Sort 소개

• Tim Sort
  • 2002년 소프트웨어 엔지니어 Tim Peters에 의해 Tim Sort가 등장함
  • Insertion Sort와 Merge Sort를 결합하여 만든 정렬 알고리즘
  • 시간 복잡도가 최선인 경우 O(N)이고, 평균과 최악의 경우 O(NlogN)인 알고리즘
  • 기존의 Merge Sort에 비해 추가적인 메모리를 적게 사용하여 다른 O(NlogN) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘
  • Python, Java SE7, Android, Google Chrome(V8), Swift 등에서 표준 정렬 알고리즘으로 채택되어 사용중임

Tim Sort의 기본 원리

• Tim sort 알고리즘
  • Insertion sort와 Merge sort를 결합한 알고리즘
  • 작은 n에 대해서는 Insertion sort가 빠르다는 사실을 이용하여 전체를 작은 덩어리(run)으로 잘라서 각각의 덩어리를 Insertion sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어임
  • 전체를 2^x개씩 잘라서 각각을 Insertion sort로 정렬하면 일반적인 Merge sort보다 덩어리별 x개의 병합 동작이 생략됨
    • Merge sort의 동작시간 : Cm X nlogn
    • Tim sort의 동작시간 : Cm X n X (logn - x) + a
    • 이 때 x값을 최대한 크게 하고, a값을 최대한 작게 하기 위해 여러 가지 최적화 기법이 사용됨

상수 C

• 알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가를 나타내는 값
• 참조 지역성 원리 : CPU가 미래에 원하는 데이터를 예측하여 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위해 사용하는 원리
  • 최근에 참조한 메모리나 그 메모리에 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아 놓는것
  • 메모리를 연속적으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면에, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도가 비교적 느림

Tim Sort의 최적화 기법

Run

• Tim sort의 동작시간에서 a를 유지하면서 x를 크게 하기 위한 방법

  • 2^x개(minrun)씩 잘라 각각을 Insertion sort로 정렬하되, 그 이후에는 Insertion sort를 진행하지 않고 덩어리(run)를 최대한 크게 만들어서 병합횟수를 줄이는 것
    1. run의 첫 두 원소의 대소 관계로 이 run를 증가하는 run, 감소하는 run이라고 정의하여 2^x개(minrun)까지는 Insertion sort를 진행하고, 그 이후의 원소에 대해서 가능한 가능한 크게 run를 만듬
    2. 이후 감소하는 run은 뒤집어서 모든 run이 증가하는 run이 되도록 변환함
       (값이 동일한 원소는 뒤집을 경우 순서가 바뀌기 때문에 감소하는 run에서는 다루지 않음)

• Tim sort에서 minrun의 크기 : min(N, 2^5 ~ 2^6) (N: 전체 원소의 개수)

  • 고정된 수로 정의하지 않는 이유는 더 느려지는 경우가 있기 때문임
  • 2개씩 병합하는 Merge sort의 특성상, run의 개수가 2의 거듭제곱이 아닌 경우 더 많은 시간이 걸림
  • 따라서 run의 개수가 2의 거듭제곱이 되도록 유동적으로 minrun 값을 정하여 사용함

Binary Insertion sort

• Tim sort에서 사용하는 Insertion sort는 Binary Insertion sort임
  • 앞의 원소들은 모두 정렬되어 있다는 전제를 기반으로 이분 탐색를 진행하여 위치를 찾음
  • 참조 지역성은 떨어지지만 한 원소를 삽입할 때 O(logn)번의 비교를 진행하기 때문에 작은 n에 대하여 시간을 좀 더 절약할 수 있음
  • 그 위치에 삽입하는 과정은 O(n)이지만, 그 위치에 삽입하고 나머지 원소를 시프트하는 연산은 빠르기 때문에 훨씬 효율적임

Run을 Merge할 때의 조건

• Tim sort에서는 하나의 run이 만들어질 때마다 스택에 담아 효율적으로 병합을 진행함
• 이때 run을 스택에 push할 때마다 스택의 맨 위의 세 run이 그림과 같이 두 조건을 만족해야함

• 두 조건을 만족하지 않는 상황이 되면, B는 A와 C 중 작은 run과 병합됨

• 병합한 후에도 스택의 맨 위의 세 run이 조건을 만족하지 않으면 조건이 만족할 때까지 병합을 진행함

• 두 조건을 만족하는 스택을 사용할 때의 장점
  1. 스택에 들어있는 run의 수를 작게 유지할 수 있음
     • 스택에 있는 모든 run은 2보다 같거나 큰 i에 대해 stack[i] > stack[i - 1] + stack[i -2]를 만족함 (피보나치 수열과 유사함)
     • 각 run의 길이가 최소 피보나치 수보다 크므로, k번째 run의 길이는 1.618^k보다 커서 k는 대략 logN보다 작거나 같음
  2. 비슷한 크기의 run과 병합할 수 있음
     • 조건을 만족하지 않을 경우 B는 A와 C 중 작은 run과 병합한다는 것은 B에서 인접한 두 run 중 가장 비슷한 run과 병합한다는 것을 의미함
     • 최소한의 메모리를 사용하여 최고의 효율을 내기 위한 방법임

2개의 Run을 Merge하는 방법

• Merge sort에서 추가 메모리를 n 사용한다는 단점을 극복하는 방법
  • 2개의 run A와 B 중 run A의 크기가 더 작은 경우
    1. 크기가 더 작은 run인 A를 복사함
    2. 이후 각 run의 시작 부분부터 크기 비교를 하여 작은 순서대로 앞을 채우면서 병합을 진행함
  • run B의 크기가 더 작은 경우
    1. 크기가 더 작은 run인 B를 복사함
    2. 각 run의 끝 부분부터 크기 비교를 하여 큰 순서대로 뒤를 채우면서 병합을 진행함
  • 두 run 중 크기가 작은 run을 담을 메모리가 필요하기 때문에, 최악의 경우 n/2의 추가 메모리를 사용함
  • run A, B를 병합하기 전, 병합을 수행할 필요가 없는 구간을 먼저 계산함

• 위 그림에 대한 해설

  • run A의 맨 앞 원소 [3, 5, 8]은 run B의 맨 앞 윈소인 9보다 작기 때문에 병합을 수행하지 않고 현재 위치에 있어도 문제가 되지 않음
  • run B의 맨 뒤 원소 [13, 15, 18, 21]은 run A의 맨 뒤 원소인 13보다 같거나 크기 때문에 이 원소들도 병합을 수행할 필요 없는 구간임
  • 이제 [11, 13], [9, 10] 부분 run만 병합을 진행하면 되기 때문에, 4번의 비교와 2개의 추가 메모리만으로 병합을 효율적으로 진행 가능함

• 병합이 필요 없는 구간을 계산하는 과정을 이분 탐색으로 진행할 경우, run의 길이가 k일 때 O(logk)의 시간이 소요됨

  • 병합이 필요 없는 구간이 없을 경우 오히려 더 늦춰질 수도 있음

Galloping

• Galloping
  • 병합하는 과정에서 추가로 사용되는 최적화 방법
  • 한 run을 계속해서 참조하는 경우 빠르게 참조하도록 동작함
  • 처음에는 화살표가 가리키고 있는 두 원소를 대소 비교하여 어느 run의 원소를 넣을지 정함 (One pair at a time mode)
  • 한 run에서 원소가 MIN_GALLOP번 연속으로 병합될 경우 Galloping mode로 전환됨
    • MIN_GALLOP : 전체 배열을 정렬하는 과정에서 Galloping mode에 들어가는 횟수가 많았다면 감소하고 아니라면 증가하여 더 효율적으로 동작하게 함
    • 이 모드에서는 2^k로 뛰어 넘으며 대소 비교를 진행함
  • 이후 다시 하나의 run에서 연속적으로 병합되지 않으면 One pair at a time mode로 돌아가 다시 하나씩 비교함

• 위 그림에 대한 해설
  • 초록색으로 색칠되어 있는 부분은 run A의 일부, run A의 일부 아래에 있는 부분은 run B의 일부임
  • run B의 원소가 3번 연속으로 병합되었기 때문에 Galloping mode로 전환됨
  • 2^k로 뛰어 넘으며 10, 30, 75와 대소 비교를 함
  • 70 < 75이므로 [45, 50, 60, 75]의 범위에서 이분 탐색을 진행하여 어느 위치까지 병합할지 결정함
  • 이후 다시 하나의 run에서 연속적으로 병합되지 않으면 One pair at a time mode로 돌아가서 하나씩 비교를 진행함

참고

• Tim sort에 대해 알아보자