Output the number of pairs that are in the wrong order in an array?

Question

For example I have the array:

int IDs[]={1,21,5,3,12,23,2};

The number of pairs that are in the wrong order is 9. The pairs are: (21, 5) (21,3) (21, 12) (21,2) (5,3) (5,2) (3,2) (12,2) (23,2).

So , my algorithm for this implies two for's:

 for(int i=0;i<IDs.length;i++)
    {
        for(int j=i+1;j<IDs.length;j++)
        {
            if(IDs[i]>IDs[j]) 
                wrong++;             
        }
    }

The problem is that this has a complexity of n² and I should have a complexity of maximum n*log n.

I think you can do this using a modified BST. Everytime you have to branch off to the left (either through adding a new left child or going further down existing nodes), you add new "wrong-order" pairs. Specifically, add a new pair for the node you just went left from, plus a pair for each of that node's descendants to the right. Try it and you'll see what I mean. — musical_coder, Dec 02 '13 at 18:44

score 0 · Answer 1 · edited May 23 '17 at 12:05

0

The number of pairs in wrong order are called the number of inversions. With this knowledge, someone can easily find a previous solution:
Counting inversions in an array

edited May 23 '17 at 12:05

Community

1
1

answered Dec 02 '13 at 18:56

mcserep

3,231
21
36

thanks a lot . hopefully i found what i need there – Moroianu Alexandru Dec 02 '13 at 19:24

Output the number of pairs that are in the wrong order in an array?

1 Answers1