개요
앞선 글에서 배열을 정렬하기 위해 하위 배열로 나누고 분할하고 정복하는 과정을 배웠습니다. 그리고 남은 일은 병합하는 일입니다. 어떻게 하면 분할된 두 개의 배열을 효율적으로 구축할 수 있을까요?
두 하위 배열에 총 n개의 요소가 있습니다. 이들을 하나로 병합하기 위해선 각 요소를 검사해야하기 때문에 최상의 경우 병합시간이 Θ(n)이 소요됩니다. 그럼 최상의 경우인 Θ(n)으로 시간내에 어떻게 병합할지 살펴보겠습니다.
풀이 - 임시 배열의 생성
분할 단계에서 저희는 array[p..r]을 array[p..q]와 array[q+1..r]로 나누었습니다. 결과적으로 이를 병합하여 배열[p..r]을 얻기 위해선 임시 배열을 만들어 하위 배열 두 개를 임시 배열에 복사하는 작업을 해야합니다. 그 전까지 array[p..r]에 값을 덮어 쓸 순 없습니다.
그러므로 merge()에선 두 임시 배열 lowHalf[]와 highHalf를 만들고 하위 배열 두 개를 담아줘야합니다. 이때 lowHalf의 크기는 얼마일까요? 하위 배열[p..q]는 q-p+1개 요소를 가지고 있습니다. highHalf는 array[q+1..r]이므로 r-q개의 요소를 가지게됩니다.
배열 [14, 7, 3, 12, 9, 11, 6, 2]를 재귀적으로 정렬하면 하위 배열들이 lowHalf와 highHalf에 어떻게 복사되는지 아래의 그림을 통해 확인해보겠습니다.
이제 lowHalf와 highHalf에 있는 정렬된 하위 배열을 array[p..r]로 병합하는 일만 남았습니다. 두 하위 배열은 정렬된 상태이므로 최솟값은 두 배열의 0번 인덱스 중 하나입니다. (두 군데 모두 같은 값이 입력된 경우 아무거나 받아도 됩니다) 병합시 비교 하나 만으로 lowHalf[0]과 highHalf[0] 둘 중 어느 것을 array[p]에 입력할지 판단 가능합니다. 위 예제에서는 highHalf[0]이 더 작은 값을 가지고 있네요. 그럼 배열 내 인덱스에 입력할 변수 세 개를 구축해보겠습니다.
1) i 는 lowHalf 에서 array 로 붙여넣지 않은 바로 다음 요소를 나타냅니다. i의 초기값은 0입니다.
2) j 는 highHalf 에서 array 로 붙여넣지 않은 바로 다음 요소를 나타냅니다. j의 초기값도 0입니다.
3) k 는 array에 붙여넣을 바로 다음 위치를 나타냅니다. k의 초기값은 p 입니다.
lowHalf 또는 highHalf 에서 array로 값을 복사합니다. 그리고 다음으로 작은 요소를 array 의 다음 위치로 복사해 넣기 위해서 k 의 값을 증가시킵니다. 그리고 lowHalf 에서 복사했다면 i 의 값을 하나 증가시키고, highHalf 에서 복사했다면 j 를 하나 증가시킵니다. 글로 설명하니 어려우시죠. 아래 그림을 확인해주세요!
그럼 다음으로 array에 복사해 넣어야 할 값은 어디에 있을까요? lowHalf[0]이 아직 선택되지 않았음을 볼 수 있습니다. highHalf[1]보다 작은 값이기 때문에 이게 다음으로 array[k]에 복사해 들어갈 값입니다. 그리고 i 는 하나 증가됩니다.
그리고 이와 같은 방식으로 계속 반복해주겠습니다.
결국에 lowHalf 또는 highHalf 중 한 배열의 값이 array에 모두 복사되게 됐습니다. 마지막으로 남은 lowHalf[2..3]을 그냥 복사하고 이 과정을 끝내주세요.
마지막으로 lowHalf에 남은 배열까지 차례대로 array에 담았습니다. 이렇게 n개의 요소를 병합하는데 Θ(n)만큼의 시간이 걸린다는것과 걸리는 시간은 하위 배열의 크기와 비례함을 알아냈습니다. 그럼 이 과정을 분석해보겠습니다.
풀이2 - 선형시간 병합 과정 분석
앞서 진행된 과정을 간단하게 요약해서 정리하겠습니다.
1. array[p..r] 에 있는 요소 각각을 lowHalf 나 highHalf 에 붙여넣기 합니다.
2. lowHalf 와 highHalf 에서 모두 붙여지지 않은 어떤 요소가 존재한다면 이 중 처음 나오는 두 개의 값을 비교한 후 더 작은 값을 array 에 붙여 넣습니다.
3. lowHalf 와 highHalf 중 하나의 모든 요소가 array 에 복사 되었다면 다른 임시 배열의 남는 모든 요소들을 다시 array 에 붙여넣습니다.
위 3단계를 실행하려면 코드가 몇 줄 필요할까요? 요소 한 개당 일정한 수 만큼의 개수가 필요합니다. 각 요소는 1단계에서 정확히 한 번씩 배열에서 lowHalf 또는 highHalf 중 하나로 복사됩니다. 2단계에서의 비교는 일정한 시간이 소요됩니다. 이 단계에선 두 요소를 비교하고 각 요소는 최대 한 번만 비교에서 이기게됩니다. 2단계와 3단계에서 각 요소는 정확히 한 번 array로 복사됩니다. 코드 한 줄의 실행 시간은 요소 당 일정 시간이 걸리는데, 하위 배열 [p..q] 에는 n개의 ㅇ소가 있기 때문에 병합하는데 걸리는 시간은 Θ(n)이 됩니다.