Pythonでリストを昇順ソートするのに必要な最小スワップ回数を求めるアルゴリズム

問題の概要

重複のない数値のリストが与えられたとき、そのリストを昇順に並べ替えるために必要な最小スワップ（要素の交換）回数を求めます。

具体例

たとえば、入力が nums = [3, 1, 7, 5] の場合を考えてみましょう。
「3 と 1 を交換」→ [1, 3, 7, 5]
「5 と 7 を交換」→ [1, 3, 5, 7]
以上の 2 回の操作で昇順に並べ替えられるため、出力は 2 となります。

アルゴリズムの手順

この問題は、「各位置に本来置かれるべき値」を順番に正しい場所へ入れ替えていくことで解くことができます。手順は以下の通りです。

1. sort_seq：元のリスト nums をソートして保持しておく
2. table：各値が現在どのインデックスに存在するかを記録する辞書を作成する
3. nums の各インデックス i と値 n に対して table[n] = i を登録する
4. swaps = 0 でカウンターを初期化する
5. i を 0 からリストの長さまで順に処理する：
   　・n = nums[i]（現在の値）、s_n = sort_seq[i]（i 番目にあるべき値）、s_i = table[s_n]（s_n の現在位置）を取得する
   　・s_n が n と異なる場合（まだ正しく配置されていない場合）は、swaps を 1 増やし、2 つの要素を交換すると同時に辞書の情報も更新する
6. ループ終了後、swaps を返す

この方法では、1 回のスワップごとに少なくとも 1 つの要素が最終的な位置に確定するため、最大でも n − 1 回の交換で必ずソートが完了します。計算量は前処理のソートが支配的となり、全体で O(n log n) と非常に効率的です。

実装コード

class Solution:
    def solve(self, nums):
        sort_seq = sorted(nums)
        table = {}

        for i, n in enumerate(nums):
            table[n] = i

        swaps = 0
        for i in range(len(nums)):
            n = nums[i]
            s_n = sort_seq[i]
            s_i = table[s_n]

            if s_n != n:
                swaps += 1
                nums[s_i] = n
                nums[i] = s_n
                table[n] = s_i
                table[s_n] = i

        return swaps


ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))

入力

[3, 1, 7, 5]

出力

2

まとめ

値ごとの現在位置を辞書で管理しながら、正しい位置にない要素を順次交換していくことで、最小のスワップ回数を線形時間で数え上げることができます。選択ソートの考え方を応用したテクニックなので、競技プログラミングやコーディング面接でも役立つパターンです。