転倒 (数学)
他の(事前-)整列性測度としては、その列からいくつかの項を消し去って完全に整列された列にするために必要な取り去る項数の最小値、列が含む整列された run の長さ及び総数、文字列をソートするのに必要な入れ替えの数の最小値などがある。標準的な比較ソートアルゴリズムは転倒数を O(n log n) で計算することができる。
列の転倒ベクトル (inversion vector) V は各 i = 2, ..., n に対して
V i = # { k ∣ k < i and A k > A i } {\displaystyle V_{i}=\#\{k\mid k<i{\text{ and }}A_{k}>A_{i}\}}
で成分が与えられる。つまり、V の各成分は、もとの列の対応する項の値より大きくなる先行項の総数である。列の転倒ベクトルの成分数は、もちろん初項に先行するそれより大きくなる項などはないので、もとの列の成分数より一つ少なくなることに注意。列の各置換はただ一つの転倒ベクトルを持ち、(完全に整列された)列の任意に与えられた置換を、その列と置換の転倒ベクトルをつかって作り出すことができる。