cpp09의 마지막 문제의 핵심인 merge-insert sort algorithm, Ford-Johnson algorithm이 뭔지 알아보자.
(“The Art of Computer Programming”의 해당 알고리즘에 대한 설명이 적힌 부분을 참조하였다.)
우선 포드 존슨 알고리즘은 비교를 통한 정렬을 할 때(comparison sort) 정렬하기 위한 최소 비교 수에 대한 고민에서 시작되었다.
n개의 원소를 정렬하기 위해 충분한 최소 비교 수를 S(n)이라고 했을 때 S(n)은 nlgn보다 낮을 수 없다.
<aside> 💡 왜 비교 횟수가 O(nlgn)을 넘을 수 없는가?
[Algorithm] 3-6. 정렬의 하한(lower bound)
</aside>
책에서 나온 가장 적은 비교가 필요한 정렬 방법은 binary insertion, tree selection, and straight two-way merging 세가지다. 세 가지 방법 모두 대략적으로 nlgn의 횟수를 가지고 있다.
binary insertion의 횟수를 B(n)이라고 하고, two-way list merging의 횟수를 L(n)이라고 했을 때,
아래 표는 n개의 원소가 있을 때 위에서 논의했던 방법들의 최대 비교 횟수이다.(tree selection 방법의 경우 tree의 구성에 따라 B(n)과 L(n) 사이이기 때문에 제외.)
표를 보면 항상 B(n) ≤ L(n)임을 알 수 있다.
그럼 원소가 5개 있다고 했을 때 비교횟수는 7개이거나 8개일 것이다. 그럼 여기서 비교횟수가 항상 7개이도록 할 수 있는가?
원소가 5개 일 때 무조건 7번 내의 비교를 통해 정렬할 수 있는 방법에 대해서 설명하겠다.
5개의 원소를 K1~K5라고 하자.