Pythonで配列をソートするために必要な最小スワップ回数を求めるプログラム

配列 nums が与えられたとき、その配列を昇順または降順のどちらかの順序でソートするために必要なスワップ（要素の交換）回数を求める問題を考えてみましょう。

例えば、入力が nums = [2, 5, 6, 3, 4] の場合、出力は 2 になります。最初、nums は [2, 5, 6, 3, 4] です。まず 6 と 4 を交換すると配列は [2, 5, 4, 3, 6] になり、続いて 5 と 3 を交換すると [2, 3, 4, 5, 6] となり昇順に整列します。つまり、この配列をソートするには 2 回のスワップが必要です。

解き方のアプローチ

この問題は、各要素が本来あるべき位置との対応関係を追跡し、循環（サイクル）を検出することで効率的に解けます。手順は以下の通りです。

• 関数 swap_count() を定義します。引数として input_arr を受け取ります。
  • pos := input_arr の各要素に対して (元の位置, 値) のタプルを格納した新しいリストを作成します。
  • pos を値に基づいてソートします。
  • cnt := 0 としてカウンタを初期化します。
  • index を 0 から input_arr のサイズ未満まで繰り返します。
    • while True ループ内で次を判定します。
      • pos[index][0] が index と一致していれば、正しい位置にあるのでループを抜けます。
      • そうでなければ、cnt を 1 増やし、swap_index := pos[index][0] として、pos[index] と pos[swap_index] の内容を入れ替えます。
  • cnt を返します。
• メインとなる solve() 関数では、swap_count(input_arr)（昇順の場合）と swap_count(input_arr[::-1])（降順の場合）の小さい方を返します。これにより、「任意の順序でソートできる」という条件に対応できます。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def swap_count(input_arr):
    pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
    cnt = 0

    for index in range(len(input_arr)):
        while True:
            if (pos[index][0] == index):
                break
            else:
                cnt += 1
                swap_index = pos[index][0]
                pos[index], pos[swap_index] = pos[swap_index], pos[index]

    return cnt


def solve(input_arr):
    return min(swap_count(input_arr), swap_count(input_arr[::-1]))


nums = [2, 5, 6, 3, 4]
print(solve(nums))

入力

[2, 5, 6, 3, 4]

出力

2

ポイントまとめ

このアルゴリズムは、ソート後の正しい位置と現在の位置の対応関係をたどりながら、一連のサイクルごとに必要なスワップ回数を数えていく方法です。計算量はソート部分が O(n log n)、スワップの検出部分が O(n) となるため、全体として O(n log n) で動作し、大規模な配列でも効率的に処理できます。