Pythonで挿入ソートを使用して配列をソートするために必要なシフト数を見つけるプログラム

配列が与えられ、その配列に対して挿入ソートを実行するように求められたとします。挿入ソートでは、配列内の各要素が配列内の正しい位置にシフトされます。配列をソートするために必要なシフトの総数を見つける必要があります。シフトの総数は整数であり、配列がすでにソートされている場合は、0を返します。

したがって、入力がinput_array =[4、5、3、1、2]のようである場合、出力は8

[4, 5, 3, 1, 2] = 0 shifts

[4, 5, 3, 1, 2] = 0 shifts

[3, 4, 5, 1, 2] = 2 shifts

[1, 3, 4, 5, 2] = 3 shifts

[1, 2, 3, 4, 5] = 3 shifts

シフトの総数は=0+ 0 + 2 + 3 + 3=8です。

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

• 長さ：=input_arrのサイズ
• temp_arr：=0で初期化されたサイズ1000001の新しいリスト
• ans：=0
• input_arrの各項目について、
  • val：=item
  • val> 0の場合、do
    • ans：=ans + temp_arr [val]
    • val：=val-（val AND -val）
  • val：=item
  • val <=1000000の間、do
    • temp_arr [val]：=temp_arr [val] + 1
    • val：=val +（val AND -val）
• ans：=length *（（length-1）/ 2のフロア値）-ans
• 回答を返す

例

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

def solve(input_arr):
   length = len(input_arr)
   temp_arr = [0] * 1000001
   ans = 0
   for item in input_arr:
      val = item
      while val > 0:
         ans += temp_arr[val]
         val -= val & -val
      val = item
      while val <= 1000000:
         temp_arr[val] = temp_arr[val] + 1
         val += val & -val
   ans = length * (length - 1) // 2 - ans
   return ans

print(solve([4, 5, 3, 1, 2]))

入力

[4, 5, 3, 1, 2]

出力

8