핵심 요약
Microsoft Developer가 forward iterator만으로 인접한 두 블록 A와 B를 교환하는 재귀 기반 알고리즘을 제시했고, 총 스왑 수는 n입니다.
구현 방법
- first와 mid를 교환한 뒤 포인터를 증가시키며 반복합니다.
- A>B인 경우 B를 앞부분으로 옮기고 남은 A1, A2를 재귀적으로 교환합니다.
- A<B인 경우 A를 중간으로 옮기고 남은 B를 재귀적으로 교환합니다.
- 한 쪽이 비면 아무 것도 하지 않습니다.
주요 결과
- 스왑 수는 항상 n이고, forward와 bidirectional 모두 같은 수를 수행합니다.
- bidirectional가 로컬리티가 더 좋아 권장됩니다.
