5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기 (+ 상대자 논증)
5개의 원소를 7번 비교로 정렬하기
정렬의 lower bound는 \(\lceil\lg{n!}\rceil\)이므로, 5개의 원소를 정렬하려면 최악의 경우 최소 7번은 비교해야 한다. (quick, merge, heap 모두 최악의 경우 8번 비교하게 된다.)
최악의 경우에도 7번만 비교하는 알고리즘의 핵심은 이미 정렬된 부분에 대해서 binary search를 적용한다는 점이다.
[!tip] 이런 류의 정렬 알고리즘의 문제점은 삽입할 위치보다 뒤쪽에 있는 원소들을 모두 한칸씩 밀어내야 한다는 오버헤드가 크다는 점을 고려해야 한다.
\(a, b, c, d, e\)
\(a > b\qquad\cdots 1\)
\(c > d\qquad\cdots 1\)
\(a > c\qquad\cdots 1\)
→ {a, c, d} 가능
\(a > c > d > e\qquad\cdots 2\) {a, c, d} 그룹에 c와 먼저 비교하게 되면 2번 비교로 끝난다.
→ {c, d, e} 가능
\(b > c > d > e\qquad\cdots 2\) {c, d, e} 그룹에 b를 삽입.
\(a > b > c > d > e\) 계 7번.
앞에서부터 \(a > b > c\)하지 않고, \({a,c,d}\)와 \({c,d,e}\)로 그룹짓는 이유도 그룹 원소 수를 3으로 유지해 비교 횟수를 2번으로 줄이기 위해서다.
[!info] 앞에서부터 차례대로 붙여나가면 원소가 4개일 때 worst comparison은 3번이 된다.
5개의 원소를 최악의 경우에도 6번 비교로 중간값 찾기
이는 알고리즘을 찾는데 상대자 논증 을 사용하기 좋은 예다.
[!info] 상대자는 선택할 수 있는 것 중 알고리즘을 가장 불리하게 만들 수 있는 것을 선택하도록 되어 있기 때문에,
상대자가 어느 쪽을 선택하더라도 같은 양의 정보를 얻을 수 있는 알고리즘을 찾아내야 한다.
이는 결정 트리에서 트리를 가능한 균형 있게 유지하는 것과 같은 맥락으로, 즉 한쪽 결과로부터 얻을 수 있는 정보량이 다른 결과로부터 얻을 수 있는 정보량과 비슷한 알고리즘이 좋은 알고리즘이라는 것이다.
x1, x2, x3, x4, x5의 중앙값을 찾는 최악의 경우를 상대자 논증으로
- 처음 비교는 아무 두 원소나 뽑아서 비교한다. (x1 < x2)
- 두 번째 비교에서 비교에 참여하지 않은 세 원소 중 아무 두 원소나 뽑아서 비교한다 (x4 < x5) 비교에 참여했던 x1, x2를 다시 비교에 참여시키면 상대자는 알아낼 수 있는 정보가 더 적은 쪽으로 응답할 수 있다.
- 세 번째 비교에서 비교에 참여하지 않은 나머지 원소 하나(x3)와 비교에 참여했던 아무 원소를 골라 비교한다. 어차피 비교에 참여하지 않은 원소는 x3뿐이고, 나머지는 다 비교에 참여했으니 어떤 것을 골라야 좋을지 알 수 없다. 상대자는 최악의 입력을 고르기 때문에 x1을 고른다고 가정한다. (x1 < x3)
- 과정3만 가지고는 x2와 x3의 대소를 알 수 없기 때문에 비교해준다. (x2 < x3)
여기까지 \( {x1 < x2 < x3} \quad \quad {x4 < x5} \) 가 된다.
- 3개 묶음 중에 중간 값과, 2개 묶음 중에 아무거나 뽑아 비교.
- 상대자 논증이니까. (x2 < x5)
- x4를 뽑게 되는 경우도 6번에서 비교는 다르게 해야 하지만 어쨌든 6번 비교로 끝낼 수 있다.
- 3개 묶음 중에 크면 큰거, 작으면 작은거 뽑고 2개 묶음 중에 비교 안한 다른거 하나 뽑아서 비교. (x3 > x4)
결과적으로
x1 < x2 < x4 < x3, x5 이므로
최악의 경우에도 6번 비교로 중간값이 x4임을 알아낼 수 있다.