3

Possible Duplicate:
Counting inversions in an array

This is a programming question that I had when I was interviewed by a company for a developer job few months ago.

Given an array A of N integers, an inversion of the array is defined as any pair of indexes (a,b) such that a<b and A[b]<A[a].

Write a function:

int inversion_count(int A[], int n);

which computes the number of inversions in A, or returns -1 if such number exceeds 1,000,000,000. For example, in the following array

A[0]=-1 A[1]=6 A[2]=3 A[3]=4 A[4]=7 A[5]=4

there are four inversions:

(1,2)  (1,3)  (1,5)  (4,5)

so the function should return 4.

I solved this question in a very common way: using double loop. 

int i, j;
long count;
for (i = 0; i < n; i++) {
   for (j = i+1; j < n; j++) {
      if (A[i] > A [j]) count++;
      if (count > 1000000000) break; // exit loop
   }
   if (count > 1000000000) break; // exit loop
}
if (count > 1000000000) return -1;
else return count;

So the running time of it is : O (nsquare), and I was told that it was not efficient. I am now thinking of a different way to solve this problem, maybe using an n log n algorithm, but I haven't figured it out yet. Any ideas?

Community
  • 1
  • 1
all_by_grace
  • 2,315
  • 6
  • 37
  • 52
  • 2
    "Given is an array A of N integers, the inversion of the array is a pair of indexes (a,b) such that a ???" Could you please fill in the "???". It looks like you dropped the end of the sentence. – David Hammen Jul 18 '11 at 15:17
  • Could you complete the statement `Given is an array A of N integers, the inversion of the array is a pair of indexes (a,b) such that a`, what is the definition of the inversion? – pstrjds Jul 18 '11 at 15:18
  • 1
    @Justin Thanks Justin Ethier for editing the post. I put a less than symbol, and forgot to highlight it as a code format, so the HTML encoder treated it as if it was an html tag. Sorry ! – all_by_grace Jul 18 '11 at 15:21

1 Answers1

1

This answer explains a O(n log n) algorithm: Counting inversions in an array.

The trick is to first sort (O(n log n)), and then use binary search to find elements (also O(n log n)) resulting in O(n log n).

Community
  • 1
  • 1
orlp
  • 112,504
  • 36
  • 218
  • 315