Content deleted Content added
Bluelink 1 book for verifiability.) #IABot (v2.0) (GreenC bot |
Add citation for inversion counting algorithm |
||
Line 23:
It does not matter if the place-based or the element-based definition of inversion is used to define the inversion number, because a permutation and its inverse have the same number of inversions.
Other measures of (pre-)sortedness include the minimum number of elements that can be deleted from the sequence to yield a fully sorted sequence, the number and lengths of sorted "runs" within the sequence, the Spearman footrule (sum of distances of each element from its sorted position), and the smallest number of exchanges needed to sort the sequence.{{sfn|Mahmoud|2000|pp=284}} Standard [[comparison sort]]ing algorithms can be adapted to compute the inversion number in time {{math|O(''n'' log ''n'')}}.{{sfn|Kleinberg|Tardos|2005|pp=225}}
===Inversion related vectors===
Line 143:
| chapter = 7-2 Basic objects
| publisher = Birkhäuser | ___location = Cham, Switzerland | year = 2016 | isbn = 331944235X }}
* {{cite book| ref = harv
|last1=Kleinberg|first1=Jon
|last2=Tardos|first2=Éva
|title=Algorithm Design
|isbn=0-321-29535-8 }}
* {{cite book | ref = harv
| |||