핵심 요약
Microsoft Developer의 글은 forward iterators만으로 비인접한 두 메모리 블록을 교환하는 구현법과, 회전과 단계적 교환으로 이를 완성하는 절차를 제시합니다.
구현 방법
- A, E를 제거하고 B 시작점과 D 시작점을 first와 mid로 잡습니다.
- first와 mid를 앞으로 이동시키며 B와 D의 원소를 교환합니다.
- B와 D의 크기에 따라 세 가지 경우를 처리하는 후속 회전으로 최종 위치를 확보합니다.
- B가 더 크면 D를 끝으로 옮기고 남은 부분을 회전
- D가 더 크면 B를 D 앞쪽으로 모은 뒤 회전
- 크기가 같으면 자동으로 정렬되며 회전으로 마무리
주요 결과
- 총 n회 교환으로 구성되며, 두 번째 단계의 회전은 n−k 교환에 해당합니다.
- 케이스에 관계없이 최종적으로 B와 D가 원하는 위치에 배치됩니다.
- forward-iterator 기반의 비인접 교환 해결책으로 제시됩니다.
