Content deleted Content added
Adding reference to Manilla, link to presortdness and examples |
→Inversion number: indicate bound on the number of inversion |
||
Line 16:
===Inversion number===
The '''inversion number''' <math>\mathtt{inv}(X)</math>{{sfn|Mannila|1984|pp318}} of a sequence <math>X=\langle x_1,\dots,x_n\rangle</math>, is the [[cardinality]] of inversion set. It is a common [[measure of presortedness|measures of (pre-)sortedness]] of a permutation{{sfn|Vitter|Flajolet|1990|pp=459}} or sequence.{{sfn|Barth|Mutzel|2004|pp=183}} This value is comprised between 0 and <math>\frac{n(n-1)}2</math> included.
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.
| |||