Content deleted Content added
Better |
Adding reference to Manilla, link to presortdness and examples |
||
Line 16:
===Inversion number===
The '''inversion number''' <math>\mathtt{inv}(X)</math>{{sfn|Mannila|1984|pp318}} of a sequence <math>X</math>, is the [[cardinality]] of inversion set. It is a common [[measure of
For example <math>\mathtt{inv}(\langle1,2,\dots, n\rangle)=0</math> since the sequence is ordered. Also <math>\mathtt{inv}(\langle n+1,n+2,\dots,2n,1,2,\dots, n\rangle)=n^2</math> as each pairs <math>(1\le i\le n < j\le 2n)</math> is an inversion. This last example shows that a sort that is intuitively sorted can still have a quadratic number of inversions.
It is the number of crossings in the arrow diagram of the permutation,{{sfn|Gratzer|2016|pp=221}} its [[Kendall tau distance]] from the identity permutation, and the sum of each of the inversion related vectors defined below.
| |||