팀 정렬의 동작방식 - 병합정렬
이제 팀 정렬의 병합정렬 방식에 대해 알아보겠습니다
팀정렬은 두 개의 run을 병합하는 2 run Merge과을 거칩니다
2 Run Merge 기본 개념
팀 정렬은 두개의 정렬된 run을 병합할 때, 추가 메모리 사용량을 최소화하기 위해
두 run 중 크기가 더 작은 run을 복사해서 사용합니다
복사한 run과 다른 run을 앞이나 뒤에서부터 비교하며 정렬된 배열로 병합합니다
2 run Merge 동작 방식
예를들어 다음과 같은 2개의 run이 있다고 가정하겠습니다
- run A =
[3, 5, 8, 11, 13] - run B =
[9, 10, 13, 15, 18, 21]
이때 run A의 크기가 더 작기 때문에 runA를 복사합니다
1회차 과정
복사한 배열의 첫 원소인 3과 runB의 첫 원소인 9를 비교합니다
3이 더 작으므로 결과 배열에 3을 넣습니다
2회차 과정
복사한 배열의 다음 원소인 5와 runB의 9를 비교합니다
5가 더 작으므로 5를 넣습니다
3회차 과정
다시 복사배열과 runB를 비교합니다
8이 더 작으므로 8을 넣습니다
4회차 과정
다시 복사배열과 runB를 비교합니다
이번에는 runB의 9가 더 작으므로 9를 넣습니다
5회차 과정
다시 복사배열과 runB를 비교합니다
이번도 runB의 10이 더 작으므로 10을 넣습니다
6회차 과정
다시 복사배열과 runB를 비교합니다
이번에는 복사한 배열의 11이 더 작으므로 11을 넣습니다
7회차 과정
임시 배열의 마지막 원소인 13과 runB의 13을 비교합니다
동일한 값의 경우 안정성을 위해 임시 배열의 값을 먼저 넣습니다
이제 임시 배열의 값을 모두 넣었으므로, 남은 run B의 원소들을 순서대로 결과 배열에 추가합니다
최종적으로 두 run의 병합정렬이 완료되었습니다
[3, 5, 8, 9, 10, 11, 13, 13, 15, 18, 21]
Galloping 최적화 방법
병합을 진행하다가 한쪽 run에서 연속으로 여러 번 선택되는 경우 팀 정렬은 Galloping 모드로 전환합니다
Galloping 모드는 하나씩 비교하는 대신,
한쪽 run에서 연속적으로 원소가 선택될 때 이를 병합하기 위한 최적화 방법입니다
Galloping 모드의 동작 방식
Galloping 모드는 다음과 같이 동작합니다
처음에는 두 run에서 원소를 하나씩 비교하여 병합을 진행합니다
이 방식을 One pair at a time mode라고 합니다
만약 한 run에서 원소가 연속적으로 일정 횟수 이상 선택되면 Galloping 모드로 전환합니다
Galloping 모드에서는 원소 비교를 1, 2, 4, 8 등과 같은 2의 거듭제곱 간격으로 점프하며 탐색합니다
탐색 중 목표값을 넘어가면, 그 구간에서 이분 탐색을 사용하여 병합 위치를 찾습니다
해당 위치까지의 원소들을 병합하여 처리합니다
Galloping 예제
- 임시 배열 A =
[10, 20, 30, 40, 50] - run B =
[1, 2, 3, 8, 9, 15, 25, 35, 45, 55]
처음 임시 배열의 원소 10과 run B의 원소를 비교할 때 run B의 원소 1, 2, 3이 연속으로 선택됩니다
이때 Galloping 모드가 활성화됩니다
Galloping 모드가 활성화된 후,
임시 배열의 현재 원소 10을 기준으로 run B의 남은 원소들을 1칸, 2칸, 4칸씩 점프하며 비교합니다
- 1칸 점프: run B의 원소 8과 임시 배열의 원소 10을 비교합니다. 10이 더 크므로 그대로 진행합니다
- 2칸 점프: run B의 원소 15와 임시 배열의 원소 10을 비교합니다
- 15가 더 크므로 10이 들어갈 위치는 8과 15 사이에 있습니다
이제 run B에서 이분 탐색을 수행하여 정확한 삽입 위치를 찾습니다.
이분탐색을 통해 8과 15 사이에 있는 원소 9와 비교합니다
10이 더 크므로 최종 삽입 위치는 9 뒤로 결정됩니다
결과적으로 run B의 원소 [8, 9]까지를 한 번에 병합한 후, 임시 배열의 원소 10을 삽입하여 결과 배열에 추가합니다
이후 다시 Galloping 모드를 종료하고, 병합을 일반적인 방식으로 계속 진행합니다
만약 동일한 조건이 또 나타나면 다시 Galloping 모드로 전환합니다
참고
