CODEWITHSUNDEEP
algorithm
Bob John
Bob John

Reputation: 3878

Calculating the number of inversions (conceptually?)

all, I'm trying to understand how exactly we are to calculate the number of inversions between two arrays.

Let's say, for example, we have the following two arrays:

A = [1, 2, 3, 4, 5, 6] B = [6, 3, 5, 4, 2, 1]

How would I calculate the number of inversions conceptually? That is, just looking at these two arrays, disregarding the coding involved.

Also, I know the convention of drawing line segments between the two arrays, but I'm trying to gain a deeper understanding here.

Thank you!

Upvotes: 2

Views: 3414

Answers (1)

Michal B
Michal B

Reputation: 280

I'm not sure what do you mean by a number of inversions of two arrays.

For one array: An inversion is a pair (a,b) where a is before b in the order but a > b. So, conceptually, you can try each pair for B. Let's start with 6, there are 5 inversions: (6,3), (6,5), (6,4), (6,2), (6,1). Next with 3, there are only 2: (3,2), (3,1). And so on, the result here is 13.

However this algorithm is pretty naive and runs O(n^2). Much better solution is based on merge sort algorithm and it runs in O(n log n). You can check it here. I assume this works only for the first array already sorted.

For two arrays: When it comes to 2 arrays (again conceptually), just type your B array above A array and draw lines connecting the same elements. The number of crossings should be the number of inversions. This is exactly how the merge-sort-based algorithm linked above works. Take a look at the picture below:

number of inversions

The result is still 13, so this method indeed works.

Upvotes: 10

Related Questions