Inversion Counting

Under Construction: Consider this content a preview of the real thing which is coming soon (hopefully).

graph LR
	ALG(["fas:fa-trophy Inversion Counting fas:fa-trophy #160;"])

	ASY_ANA(["fas:fa-check Asymptotic Analysis #160;"])
    click ASY_ANA "./math-asymptotic-analysis"

	MS(["fas:fa-check Merge Sort #160;"])
    click MS "./sorting-merge"

	ASY_ANA-->ALG
    MS-->ALG

Count the number of inversions in an array. An inversion is two items that are out of order. For instance, in the array: [1][3][2] the numbers 3 and 2 represent an inversion.

This algorithm is essentially the same as merge sort with the exception that it keeps track of inversions while sorting.

History

Deep rooted in mathematics, the concept of inversion dates back to 1750 when G. Cramer used them as a device for solving linear equations¹.

Inversion number is the cardinality of the inversion set. Measure the sortedness or a particular permeation.

Applications

The typical use of such algorithms is comparing preferences between users. The number of inversions between user A’s ranking of products and users B’s ranking of products represents how similar their affinities are.

• Collaborative Filtering Voting theory. 独Collaborative filtering. 独Measuring the “sortedness” of an array. 独Sensitivity analysis of Google’s ranking function. 独Rank aggregation for meta-searching on the Web. 独Nonparametric statistics (e.g., Kendall’s tau distance)

Pseudo Code

A = input array
inversions = 0

if length of A is 1
    return 0

count:
    A1 = first half of A
    A2 = second half of A

    inversions += recursively count\sort A1
    inversions += recursively count\sort A2

    i = 1
    j = 1

    for k = 1 to n
        if A1[i] < A2[j]
            A[k] = A1[i]
            i++
        else
            A[k] = A2[j]
            j++
            inversions += # of items remaining in A1

    return inversions
            

Asymptotic Complexity

$O(n \log n)$

Source Code

Full Repo

Relevant Files:

• inversions.h
• inversions.c
• inversions_test.c

Click here for build and run instructions

Exercises

1. Answer me these questions three:
   a. What is your name?
   b. What is your quest?
   c. What… is the air-speed velocity of an unladen swallow?

   Answers (click to expand)

   1. It is Arthur, King of the Britons
   2. To seek the Holy Grail
   3. What do you mean? An African or European swallow?

2. Do I make you randy? Yeah, do I?

   Answers (click to expand)

   [Click here](list-data-struct-sorted-array-answers) for the answers