이전 글
Exercise 02: PmergeMe
구현에 대해 다룰 것이다. 다만, 참고만 하자.
만약 이해가 안된다면, 이전 글을 읽고 오자. 이전 글이 완벽하게 이해가 되었다는 가정 하에 이번 글을 작성하였다.
편의상 $b_k$(작은 숫자들의 수열)를 pending-elmenet라고 하겠다.
구현
구현을 할 때 까다로웠던 점이 몇 가지 있다.
- main-chain을 sort하기 위해 들어간 재귀에서 main-chain의 순서가 바뀌면 재귀 밖의 pending-element의 순서도 그에 따라 바뀌어야 한다.
- 재귀의 재귀의 main-chain의 순서가 바뀌면, 재귀 밖의 밖의 pending-element도 순서가 바뀌어야 한다.
- $b_k$를 삽입할 때 binary-search의 범위를 $a_{k-1}$로 잡아야 한다. 즉, $b_k$와 쌍이 되는 $a_k$를 알고 있어야 한다.
- 다음 야곱스탈 수가 size를 넘어서면, size부터 이전 야곱스탈 수까지의 순서로 삽입해야 한다.
의사코드는 다음과 같다.
Algorithm 1: merge_insertion_sort
Require: size, toSortArr
if size < 1 then
return
end if
Initialize arrays mainChain and pendingElm with index
merge_insertion_sort(size/2, mainChain)
Update indices of mainChain and pendingElm
Initialize remember array with pairs of elements from mainChain and pendingElm
if size is odd then
Add last element of toSortArr to the end of pendingElm
end if
while current Jacobsthal number ≤ size/2 do
(Insert elements from pendingElm into mainChain using binary search,
find end range by remeber array)
(Insert in order from current Jacobsthal number to last Jacobsthal number)
end while
for i from size of pendingElm to last Jacobsthal number do
(Insert elements from pendingElm into mainChain using binary search,
find end range by remeber array)
end for
Replace toSortArr with mainChain
하나하나 살펴보자. 예시로, [8, 1, 2, 10, 9, 5, 6, 7, 3, 4]의 수열을 정렬한다고 해보자.
먼저 mainChain과 pendingElm을 인덱스를 기억하며 init한다.
depth = 0
toSortArr = [8:0, 1:1, 2:2, 10:3, 9:4, 5:5, 6:6, 7:7, 3:8, 4:9]
size = 10
mainChain = [8:0, 10:1, 9:2, 17:3, 4:4]
pendingElm = [1:0, 2:1, 5:2, 6:3, 3:4]
다음 merge_insertion_sort를 size / 2, mainChain을 인자로 재귀적으로 호출한다.
다시 mainChain과 pendingElm를 init한다.
depth = 1
toSortArr = [8:0, 10:1, 9:2, 7:3, 4:4]
size = 5
mainChain = [10:0, 9:1]
pendingElm = [ 8:0, 7:1]
다시 재귀를 호출하여 mainChain과 pendingElm을 init한다.
depth = 2
toSortArr = [10:0, 9:1]
size = 2
mainChain = [10:0]
pendingElm = [ 9:0]
다음 재귀는 size가 1이기 떄문에 들어가자마자 빠져나온다.
이제 mainChain과 pendingElm의 순서와 인덱스를 toSortArr를 기반으로 업데이트 해준다.
mainChain = [10:0]
pendingElm = [ 9:1]
이제 야곱스탈 순서대로 pendingElm을 mainChain에 삽입해준다. 인덱스 0번째는 항상 mainChain의 맨 앞에 들어간다.
mainChain = [9:1, 10:0]
이제 toSortArr를 mainChain으로 업데이트 해주고, 재귀를 빠져나온다(레퍼런스를 활용해보자?). 재귀를 빠져나온 직후, 다음과 같이 된다.
depth = 1
toSortArr = [8:0, 10:1, 9:2, 7:3, 4:4]
size = 5
mainChain = [9:1, 10:0]
pendingElm = [8:0, 7:1]
이제 다시 인덱스와 순서를 업데이트 해준다. (먼저 pendingElm의 순서를 mainChain의 저장된 인덱스와 동일하게 바꿔주고, 각각의 인덱스를 toSortArr를 기반으로 업데이트한다.)
mainChain = [9:2, 10:1]
pendingElm = [7:3, 8:0]
각각의 쌍을 기억해준다.
remember_array = [9:7, 10:8]
사이즈가 홀수(5)이기 때문에 toSortArr의 마지막 원소를 pendingElm에 추가해준다. 결과적으로 다음과 같이 된다.
depth = 1
toSortArr = [8:0, 10:1, 9:2, 7:3, 4:4]
size = 5
remember_array = [9:7, 10:8]
mainChain = [9:2, 10:1]
pendingElm = [7:3, 8:0, 4:4]
이제 야곱스탈 수에 따라 원소를 mainChain에 삽입한다. 먼저 pendingElm의 0번째는 항상 mainChain의 맨 앞이다.
current_jacobsthal = 1
last_jacobsthal = 0
mainChain = [7:3, 9:2, 10:1]
pendingElm = [7:3, 8:0, 4:4]
다음 야곱스탈 수는 3이므로, pendingElm의 2번째 원소를 삽입해준다. 이 때, 이분탐색의 end range를 remember_array를 통해 찾는다. pendingElm의 2번째 원소 4의 pair는 없으므로, 마지막 원소라는 뜻이다. end range는 mainChain의 사이즈가 된다 (7, 9, 10 중에서 탐색).
다음은 pendingElm의 1번째 원소를 삽입해준다. pendingElm의 1번째 원소 8의 pair는 pair는 remember array상 10이므로, end range는 1이 된다(7, 9 중에서 탐색).
결과적으로 다음과 같이 된다.
current_jacobsthal = 3
last_jacobsthal = 1
mainChain = [4:4, 7:3, 8:0, 9:2, 10:1]
pendingElm = [7:3, 8:0, 4:4]
이제, toSortArr를 mainChain으로 바꿔주고, 재귀를 탈출한다. 탈출한 직후는 다음과 같다.
depth = 0
toSortArr = [8:0, 1:1, 2:2, 10:3, 9:4, 5:5, 6:6, 7:7, 3:8, 4:9]
size = 10
mainChain = [4:4, 7:3, 8:0, 9:2, 10:1]
pendingElm = [1:0, 2:1, 5:2, 6:3, 3:4]
다시 똑같은 과정을 거쳐준다. 자세한 설명은 생략한다.
remember_array = [4:3, 7:6, 8:1, 9:5, 10:2]
mainChain = [4:4, 7:3, 8:0, 9:2, 10:1]
pendingElm = [3:8, 6:6, 1:1, 5:5, 2:2]
mainChain = [3:8, 4:4, 7:3, 8:0, 9:2, 10:1]
mainChain = [1:1, 3:8, 4:4, 7:3, 8:0, 9:2, 10:1]
mainChain = [1:1, 3:8, 4:4, 6:6, 7:3, 8:0, 9:2, 10:1]
mainChain = [1:1, 2:2, 3:8, 4:4, 6:6, 7:3, 8:0, 9:2, 10:1]
mainChain = [1:1, 2:2, 3:8, 4:4, 5:5, 6:6, 7:3, 8:0, 9:2, 10:1]
와 같은 과정을 거쳐 정렬이 완료된다.
마무리하며..
사실 이 과제를 처음할 때, main-chain의 정렬을 그냥 냅다 std::sort를 갖다 박았다. 그리고 나서는 ex00, ex01때문에 한 번씩 터져 평가를 총 6번을 받은 상태였는데, 중간에 평가자로 오신 분중 goat이신 분이 “이건 포드 존슨이 아니다!”라고 못박아주시면서 TAOCP를 알려주셨다. 인덱스를 통해 기억하는 방법도 힌트를 주셨다. 감사를 표합니다,,
대충 그 후로 2주정도 ex02에 갖다박은 것 같은데, 해볼만한 가치가 있었다. 삽질도 좀 많이했고.. 여튼 과제 진행하시는 분들 화이팅입니다. 이해안되는 부분은 댓글 남겨주십쇼.