2

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!

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
Bob John
  • 3,688
  • 14
  • 43
  • 57
  • That question seems more involved in trying to compute the specific number of inversions for a permutation using a sorting algorithm under a specified time. I'm strictly trying to understand the inversion process intuitively, later to try and solve the problems such as the one you've linked to. – Bob John Aug 06 '12 at 04:41
  • Inversion of which operators? Generic swaps, side-by-side element swaps, shifts, rotations, ...? – KillianDS Aug 06 '12 at 05:21

1 Answers1

10

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.

Community
  • 1
  • 1
Michal B
  • 280
  • 5
  • 10