NOMURA プログラミングコンテスト 2021 C - Odd Even Sort (500)
バブルソートでおおよそ$ \frac{N^2}{2}回操作すればできることなので、基本バブルソートと同様に行う
3個の時の操作列は事前に全部列挙して埋め込む
前の方から順にソートしていく
既にソート済みの値は飛ばす
交換したい値のインデックスを二分探索で求める
奇数回目かつインデックスが偶数の場合
現在のインデックスが偶数なら現在の位置でスワップする
隣が交換したい値だったら、その位置も更新する
奇数なら現在の右の位置でスワップする
隣が交換したい値だったら、現在の位置でスワップし、その位置も更新する
偶数回目かつインデックスが奇数の場合
現在のインデックスが奇数なら現在の位置でスワップする
隣が交換したい値だったら、その位置も更新する
偶数なら現在の右の位置でスワップする
隣が交換したい値だったら、現在の位置でスワップし、その位置も更新する
交換回数の偶奇が揃ったので、後ろから交換したい値をスワップし続けて前に持ってくる
スワップされていないのが残り3個になったら埋め込んだ操作列を使って残りをスワップする
スワップがボトルネックで$ \mathcal{O}(N^2)