Grid Sort

왼쪽 열부터 차례대로 완성한다. $i$열을 완성할 때는 두 목표 수 $i$와 $N+i$를 함께 살펴보고, 이미 완성한 열은 건드리지 않는다.

• 두 목표 수가 같은 행에 있다면, 잘못된 행에 있는 수가 놓인 열에서 세로로 한 번 교환한다. 이제 두 수가 각각 올바른 행에 있으므로, 각 수를 가로 교환으로 $i$열까지 옮긴다.
• 두 목표 수가 서로 다른 행에 있다면, 각 수를 현재 행에서 $i$열까지 옮긴다. 두 수의 행이 뒤바뀌어 있다면 마지막에 $i$열에서 세로로 한 번 교환한다.

각 수의 현재 위치를 저장하고 교환할 때마다 갱신한다. 교환 목록을 저장한 뒤 그 길이와 목록을 출력하면 된다. 시간 복잡도와 교환 목록을 포함한 공간 복잡도는 모두 $O(N^2)$이다.