Pythonで配列をソートするために必要なスワップの数を見つけるためのプログラム

numsという配列があり、numsを昇順または降順の任意の順序で並べ替えるのに必要なスワップの数を見つける必要があるとします。

したがって、入力がnums =[2、5、6、3、4]のような場合、最初はnumsが[2、5、6、3、4]であるため、出力は2になります。番号6と4を入れ替えると、配列は[2,5,4,3,6]になります。次に、番号5と3を入れ替えると、配列は[2,3,4,5,6]になります。したがって、配列を昇順でソートするには2つのスワップが必要です。

これを解決するには、次の手順に従います-

• 関数swap_count（）を定義します。これにはinput_arr
  が必要です
  • pos：=input_arrの各アイテムのタプル（item_postion、item）を含む新しいリスト
  • input_arrの項目に従ってリストの位置を並べ替えます
  • cnt：=0
  • 0からinput_arrのサイズまでの範囲のインデックスについては、
    • Trueの場合は、
      • pos [index、0]がindexと同じ場合、
        • ループを終了します
      • それ以外の場合、
        • cnt：=swap_count + 1
        • swap_index：=pos [index、0]
        • （pos [index]、pos [swap_index]）の値を交換します
  • return cnt
• メインの関数/メソッドから、次のようにします-
  • （swap_count（input_arr）、swap_count（input_arrの逆順））の最小値を返します

例

理解を深めるために、次の実装を見てみましょう-

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