Is there an algorithm to count array inversions in linear time?

Question

I know that the number of inversions in an n-element array can be counted in O(n log(n)) operations using an enhanced merge sort.

However, I came across a different solution, which somehow manages to count the number of inversions in O(n) time, provided that the input is a permutation of (1, 2, 3, ..., n−1, n):

EDIT:-

I am sorry for the code I pasted as it doesn't work in all the cases . Actually this code was used for this question and it passed all the cases . But I am still leaving the code so that it may serve as some intuition and maybe a linear time solution for this problem will come up.

NOTE :- The Below Mentioned Code is Incorrect.

/* int in = 0;
    for (int i = 0; i < n; i++) {
        a[i] = a[i] - i - 1;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > 0)
            in = in + a[i];
        else if (a[i] < -1)
            in = in - a[i] - 1;
    } */

Now the question is can we come up with a linear time solution for this problem ?

Is that code copied correctly? `i` being modified in both inner and outer `for` loops? — Mike, Jun 02 '14 at 17:25
@Mike yeah I corrected it . Seems like stackoverflow edited it wrongly. — Raman Singh, Jun 02 '14 at 17:28
it looks like you don't handle `a[i] == -1` or `a[i] == 0`. is `in = in - a[i] - 1;` supposed to read `in = in - a[i] + 1;`? — Steve Cox, Jun 02 '14 at 17:31
@Steve It's not my algo . I just saw it someplace and found it interesting but wasn't able to understand it . And also in the first loop a[i] has been replaced with a[i]-i-1 . — Raman Singh, Jun 02 '14 at 17:33
I don't understand what you mean by "we use divide and conquer paradigm and follow the merge sort to get count O(nlog(n))" can you explain what algorithm you are talking about. Maybe put that code here also. What problem does that solve? How is that problem different from the current problem at hand? Since you also said "But I found a slightly different question..." — Spundun, Jun 02 '14 at 17:34
@Spundum Here is the link to counting inversions by merge sort http://www.geeksforgeeks.org/counting-inversions/ . — Raman Singh, Jun 02 '14 at 17:35
@Spundum The merge sort method is a generalized algorithm which will work for any type of array , but the above algorithm is applicable only when the array is a random permutaion of 1,2,3...N. For eg if N =4 . Then array can be 2,4,3,1. — Raman Singh, Jun 02 '14 at 17:37
@AshishGupta Please be more careful with your edits. The `{}` you added changed the meaning of the code (in general, you shouldn't be adding / removing things like `{}` to / from other people's code). — Bernhard Barker, Jun 02 '14 at 18:44
Voting to close this as the code doesn't actually work (as mentioned in the answers) (that seems like the correct action to me). But then again, others might similarly find that claimed solution and look for an explanation, so I don't know (if possible, we should probably take it up with whomever posted it where it's posted, in hopes of an amendment or removal) ... or perhaps there's a typo in the solution, in which case it should be closed. — Bernhard Barker, Jun 02 '14 at 23:20

score 3 · Accepted Answer · answered Jun 02 '14 at 18:21

3

The obvious answer is that it doesn't. For example, for n = 4 and a = {2, 3, 4, 1}, you code gives the answer 5, even though the correct inversion count is clearly 3.

answered Jun 02 '14 at 18:21

Ilmari Karonen

49,047
9
93
153

Alfred Huang · Answer 2 · 2014-06-02T18:27:24.997

1

The approach is WRONG! Consider the example below!

int a[] = { 2, 3, 1 };

int in = 0;

for (int i = 0; i < n; i++) {
    a[i] = a[i] - i - 1;
}

// a[] = { 1, 1, -2 };

for (int i = 0; i < n; i++) {
    if (a[i] > 0)
        in = in + a[i];
    else if (a[i] < -1)
        in = in - a[i] - 1;
} 

// in = 1 + 1 - (-1) = 3

The correct answer is 2 but it returns 3 here!

edited Jun 02 '14 at 18:27

answered Jun 02 '14 at 18:20

Alfred Huang

17,654
32
118
189

Is there an algorithm to count array inversions in linear time?

NOTE :- The Below Mentioned Code is Incorrect.

2 Answers2

Linked