Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to extract useful info from some data and this makes me think how to do it efficiently. I will try to explain the problem with math terms.

If we have a sequence of numbers $A=(a_{1}\space a_{2}\dots a_{n})$ and we want to count the number of inversions, ie the number of pairs $(a_{i},a_{j}), 1\leq i < j\leq n$ and $a_{i}>a_{j}$.

I want to find a good algorithm that will solve this problem.

I am looking for an algorithm that is better from the trivial one that solves the problem in polynomial time.

share|improve this question
2  
The obvious algorithm that compares all pairs is already quadratic, so asking for a polynomial time algorithm doesn't make much sense. The question is whether you can do better than quadratic. "Better than polynomial" also doesn't make any sense, since even a constant run time is polynomial. –  joriki Nov 12 '11 at 14:35
    
Sorry about that. I am not really into algorithms but i am trying. I am reading books and i try to apply what i learn. –  practic_pom Nov 12 '11 at 14:59
    
It would be interesting to describe the real life problem that you are trying to solve. –  pressy_paris Nov 13 '11 at 9:18
1  
Why did you edit the question without correcting the errors I pointed out? Also, I believe you mean $1\le i\lt j\le n$ where it says $1\le i\le n$? –  joriki Nov 13 '11 at 9:48
    
I think the question title is misleading and not specific enough. Maybe "Counting inversions in lists algorithmically" is more appropriate. Also, tags "statistics" and "optimization" should be removed in favor of "computer-science". –  Raphael Nov 13 '11 at 12:48

2 Answers 2

up vote 2 down vote accepted

As stated by @joriki, the trivial algorithm that compares all values pairwise has runtime in $\Theta(n^2)$.

A better runtime can be achieved by leveraging balanced binary search trees, e.g. AVL trees. Assume you have AVL trees that store in every node $v$ the number of nodes $t(v)$ in the subtree rooted in $v$; this does not change the runtime characteristics of AVL trees.

Now you take your list and an empty tree and insert the elements one by one. If you have no reversals, every element will end up as the right-most node after inserting. Conversly, the number of reversals an element causes can be read off while inserting; whenever you descend to a left child, add $t(v)$ of the right child you did not go to, and add $1$ if the father is properly larger than the element you insert.

The proposed alorithm has runtime in $\cal{O}(n\log(n))$ as insertion in AVL trees is in $\cal{O}(\log(n))$.

Edit: Apparently you can do better for permutations.

share|improve this answer
    
That's really cool. I was thinking that i can use mergesort but didn't figure out how. Now i have to read about trees. Thanks for the answer. –  practic_pom Nov 13 '11 at 10:07
    
@practic_pom: Several of the answers to the questions I linked to in my answer use mergesort. –  joriki Nov 13 '11 at 10:10
1  
@practic_pom, if you like this answer, maybe you want to given it a 1 and mark it as an answered question. –  Emmad Kareem Nov 13 '11 at 10:12
    
@practic_pom You might want to look into "Introduction to Algorithms" by Cormen et al (if you have not done so already). –  Raphael Nov 13 '11 at 10:56
    
@Raphael I will, i already ordered that book. –  practic_pom Nov 13 '11 at 11:14

The reason you didn't find a solution to this by searching seems to be that the more usual term for what you call a "reversal" is "inversion". Searching for algorithms counting the number of inversions generates lots of hits, including these two questions on stackoverflow with lots of answers:

Counting inversions in an array and How to find the number of inversions in an array.

share|improve this answer
    
Very interesting links. I think i am gonna use some code from them. –  practic_pom Nov 13 '11 at 10:16
    
+1; I knew there was another name for it. Damn you, brain! –  Raphael Nov 13 '11 at 12:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.