🛠️ 팀 정렬 (Tim Sort)의 원리
팀 정렬은 삽입정렬과 병합정렬을 합친 알고리즘입니다
팀 정렬은 데이터 크기가 작은 경우 삽입정렬이 퀵 정렬보다 더 좋은 성능을 낸다는 것을 주목했습니다
전체 데이터를 작은 블록으로 나누고, 각 블록에 대해 삽입 정렬을 적용하면 작은 데이터 집합에서
참조 지역성의 이점을 활용할 수 있습니다
이렇게 정렬된 작은 블록들을 다시 병합 정렬로 결합하면, 안정적이면서도 빠른 정렬이 가능합니다
팀 정렬은 이러한 점를 기반으로, 전체 데이터를 작은 블록으로 나눠 각각을 삽입 정렬한 뒤,
블록들을 병합 정렬로 합쳐 최종 정렬을 수행합니다
🤔 무엇을 최적화 해야할까?
알고리즘의 실제 수행 시간은 다음과 같이 표현할 수 있습니다.
C × nlogn + α
팀 정렬은 이 수행 시간을 최소화하기 위해 데이터셋을 일정 크기의 블록으로 나누고,
각 블록 내부를 삽입 정렬로 정렬합니다
팀 정렬에서 사용하는 블록 크기는 일반적으로 2^x인데,
이렇게 하면 병합 정렬 과정에서 블록 간 병합정렬의 횟수가 줄어듭니다
일반적인 병합 정렬은 블록의 수가 많기 때문에 병합 과정이 여러 번 반복되어야 하지만,
팀 정렬은 미리 삽입 정렬을 통해 정렬된 블록을 만듦으로써 병합 과정의 연산을 줄일 수 있습니다
이러한 접근을 수식으로 나타내면 팀 정렬의 수행 시간은 다음과 같이 표현할 수 있습니다
C_m × (n × (logn - x)) + α
여기서 새롭게 추가된 수식의 정의는 다음과 같습니다
- C_m은 병합 연산에 관련된 상수
- x는 블록의 크기를 결정하는 변수(블록 크기를 2^x로 정의)
- 따라서 팀 정렬을 최적화하려면, 블록 크기인 x의 값을 최대화하고 α를 최소화하면 효율적인 정렬이 가능합니다
🛠️ 팀 정렬의 최적화 방법 - (삽입 정렬)
실제 예시 배열을 통해 팀 정렬의 최적화 방법에 대해 알아보겠습니다
다음과 같은 배열을 팀 정렬을 통해 오름차순 정렬할 것입니다
[4, 7, 9, 12, 11, 13, 8, 5, 3, 2, 15, 18, 21]
📌 구간 탐색
먼저 팀 정렬은 데이터를 처음부터 순회하면서 증가하는 구간 혹은 감소하는 구간을 탐색합니다
해당 구간을 찾는 이유는 이미 정렬된 구간을 최대한으로 활용하기 위함입니다
이어서 블록의 최소단위인 2^x 의 x를 결정해서 탐색을 진행합니다
📌 전제 조건
전체 데이터 N = 13개입니다
이때, 최소 범위인 2^x 를 4로 설정하고, x는 2로 설정하겠습니다
만약 최소 범위보다 작은 블록이 생긴다면 삽입 정렬을 활용해서 블록의 범위를 확장해야합니다
📌 첫번째 탐색
4 -> 7 -> 9 -> 12 탐색을 통해, [4, 7, 9, 12]과 같이 증가하는 구간의 블록을 구성합니다
해당 구간은 최소 범위인 4를 충족하므로 별도의 삽입정렬 없이 다음 구간을 탐색합니다
📌 두번째 탐색
이어지는 값은 이전보다 작은 11입니다
증가하는 구간이 종료되는 지점이므로, 새롭게 블록을 구성해야합니다
11 -> 13 과정을 통해 증가하는 블록을 구성했습니다
이번 블록은 첫번째 탐색결과와 다르게, 블록의 최소범위보다 작은 크기를 갖습니다
따라서 이전 탐색 결과 만들어진 블록에 삽입 정렬로 추가합니다
그 결과 [4, 6, 9, 11, 12, 13] 의 블록이 만들어졌습니다
📌 세번째 탐색
8 -> 5 -> 3 -> 2 탐색을 통해 감소하는 구간의 블록이 만들어졌습니다
이번에는 최소범위인 4를 충족하므로 별도의 삽입 과정은 없습니다
여기서 감소하는 블록은 증가하는 블록이 되도록 뒤집어 줍니다
그 결과 [2, 3, 5, 8] 형태의 구간이 됩니다
이유는 다음과 같습니다
🎈 병합 정렬
삽입 정렬 이후, 이어지는 병합 과정에서 이점을 얻기 위함입니다
병합정렬은 두가지 오름차순 배열을 병합할 때, O(n)의 시간복잡도를 가질 수 있기 때문에 효율적입니다
따라서 팀 정렬은 블록을 증가하향으로 통일시켜
병합 단계에서 일관된 정렬 조건으로 빠르게 병합정렬할 수 있도록 합니다
🎈 안정 정렬
팀 정렬은 안정정렬입니다
그리고 이것을 위해, 팀정렬은 블록들을 증가하는 구간으로 통일했습니다
감소하는 구간을 병합하기 위해서는
기존 원소의 상대적 순서를 변경하지 않고 역방향 병합을 진행해야 합니다
하지만 이것은 구현도 까다롭고 같은 값을 가진 요소의 순서가 뒤집힐 수 있습니다
따라서 감소하는 구간을 증가하는 구간으로 뒤집어서 증가하는 구간이 되도록 통일시키고,
안정정렬을 보장합니다
📌 네번째 탐색
15 -> 18 -> 21순으로 탐색해서 증가하는 구간을 만들었습니다
하지만 최소범위보다 작습니다
따라서 삽입 정렬을 통해 앞선 배열에 추가합니다
그 결과, [2, 3, 5, 8, 15, 18, 21] 형태의 블록이 완성됩니다
📌 탐색 종료
이제 두개의 큰 블록이 형성되었습니다
[4, 6, 9, 11, 12, 13]와 [2, 3, 5, 8, 15, 18, 21]입니다
🔎 팀 정렬의 일반적인 최소범위 구간
팀정렬의 각 구간을 run이라고 부르며, 구간의 최소범위를 minrun이라고 합니다
일반적으로 팀정렬의 minrun은 전체 원소의 개수인 n에 따라
Math.min(n, 2^5 ~ 2^6)로 정의합니다
minrun을 32나 64로 고정하지 않는 이유는,
데이터 개수에 따라 정렬 성능이 오히려 나빠질 수 있기 때문입니다
예를 들어, 전체 원소 수가 N = 1088이고 minrun = 32로 고정한다면
run 개수 = 1088 / 32 = 34개가 됩니다
하지만 병합 정렬은 2의 거듭제곱 개수의 run을 병합할 때 가장 효율적으로 동작합니다
즉, 34는 2^5 = 32보다 커서 병합 과정이 불균형하게 형성되고,
병합 횟수가 증가하며 전체 정렬 시간도 더 길어질 수 있습니다
따라서 Tim Sort는 minrun 값을 유동적으로 조정하여 run의 개수를 2의 거듭제곱에 가깝게 유지합니다
앞선 예시에서는 minrun = 34로 설정하면 run 개수는 약 1088 / 34 ≈ 32개가 되어
병합 단계에서 더 효율적인 정렬이 가능합니다
🚀 이진 삽입 정렬 (Binary Insertion Sort)
팀 정렬에서 사용하는 삽입정렬은 일반적인 삽입정렬과
다른 이진삽입 정렬 방법을 선택합니다
기존 삽입정렬은 삽입해야할 위치를 찾을 때까지 비교해서 O(n)번의 시간복잡도가 발생하지만
이진 삽입정렬은 앞 원소들이 모두 정렬되었다는 가정으로 동작하므로
O(log n)번의 비교를 통해 시간을 절약할 수 있습니다
다만 이진 삽입정렬은 삽입 위치를 찾는 과정에서 메모리 접근이 불연속적으로 이루어지기 때문에
참조 지역성이 떨어지는 경우가 존재합니다
즉, 비교 횟수는 훨씬 더 줄어들지만 일반 삽입정렬보다 더 느릴 수 있는 케이스도 존재합니다
✍️ 결론
팀 정렬은 데이터를 순회하며 증가/감소 run을 나누고,
run의 길이가 minrun보다 짧다면 해당 run 내부에서 삽입 정렬로 확장합니다
감소 run은 뒤집어 모두 증가 run으로 만들며, 이후 병합 정렬로 처리합니다
삽입 정렬은 일반 방식이 아닌 이진 삽입 정렬을 사용하여 비교 횟수를 줄입니다
참고
