転倒数 アルゴリズム - kira924ageの雑記帳

転倒数 (inversion number) とは? 数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき, i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という. たとえば a = {3, 1, 5, 4, 2} のとき, i < j かつ a_i > a_j となっている組は, (3, 1), (3, 2), (5, 4), (5, 2), (4, 2) の 5組であるから転倒数は 5 となる. (添字ではなく要素の組を列挙した) 転倒数は下記のようなバブルソートを行った際の交換回数と等しくなることが知られている. 一回の交換で反転数は1減少し, ソートが完了すると反転数は0となるのでそれはそう. #!/usr/bin/env python3 def bubble_sort(A): cnt = 0 for i