원형 순열 정렬

원형 배열이므로 최종 상태는 $1,2,\ldots,N$의 회전 중 하나이면 된다.

값 $s$를 시작으로 하는 순서

$$s,s+1,\ldots,N,1,2,\ldots,s-1$$

를 목표로 잡고, 현재 순열을 이 선형 순서로 정렬한다고 하자. 이때 필요한 인접 교환 횟수는 현재 순열에서 이 목표 순서에 대한 inversion의 개수와 같다.

각 $s$에 대한 inversion 개수를 $I_s$라고 하자. $I_1$은 $O(N^2)$에 직접 구할 수 있다. $s$에서 $s+1$로 넘어갈 때, 값 $s$는 목표 순서에서 맨 앞에서 맨 뒤로 이동한다. 현재 순열에서 값 $s$의 위치를 $pos_s$라고 하면 다음이 성립한다.

$$I_{s+1}=I_s+(N-pos_s)-(pos_s-1)$$

따라서 모든 $I_s$를 $O(N)$에 갱신할 수 있다.

원형 순열에서는 항상 어떤 $s$에 대해

$$I_s \le \left\lfloor \frac{N^2}{4} \right\rfloor$$

가 성립한다. 그러한 $s$를 하나 고른 뒤, 목표 순서에 대한 inversion을 하나씩 없애는 방식으로 버블 정렬을 수행하면 된다. 이때 수행한 교환 횟수는 정확히 $I_s$이다.

전체 시간 복잡도는 $O(N^2)$이고, 출력하는 연산 수는 제한을 넘지 않는다.