先頭から順に正しい要素と入れ替えることで必ず \(N-1\) 回以下の操作で目的を達成できます。

例

5 2 3 8 4 9 6 7 1
  ↓ 1を正しい位置に移動する
1 2 3 8 4 9 6 7 5
  ↓ 2は正しい位置にあるので何もしない
1 2 3 8 4 9 6 7 5
  ↓ 3は正しい位置にあるので何もしない
1 2 3 8 4 9 6 7 5
  ↓ 4を正しい位置に移動する
1 2 3 4 8 9 6 7 5
  ↓ 5を正しい位置に移動する
1 2 3 4 5 9 6 7 8
  ↓ 6を正しい位置に移動する
1 2 3 4 5 6 9 7 8
  ↓ 7を正しい位置に移動する
1 2 3 4 5 6 7 9 8
  ↓ 8を正しい位置に移動する
1 2 3 4 5 6 7 8 9

この操作を行う際、「現在 \(A\) の中で \(i\) がどこにあるか」を配列の中から毎回探すと、最悪 \(\Theta(N)\) 時間、全体で \(\Theta(N^2)\) 時間かかるケースが存在し、TLE(実行時間制限超過)となります。

そこで配列 \(A\) の他に「\(A\) の中で値 \(i\) がある位置を表す配列 \(\mathrm{pos}\)」を用意し、同時に更新することにします。 例えば \(A=(3,1,2,4)\) のとき、\(\mathrm{pos}=(2,3,1,4)\) となります。
これにより「現在 \(A\) の中で \(i\) がどこにあるか」は \(\mathrm{pos}[i]\) を参照することで \(O(1)\) で求めることができ、全体で \(O(N)\) 時間で問題を解くことができます。