[Original post has malformed and or illegal xhtml constructs – mainly due to the unescaped ‘<‘ within the C++ code:
http://datamininginsight.blogspot.com/2007/01/count-number-of-inversions-in-sequencec.html]
An inversions in a sequence A1,A2,…,An of n different integers is defined as a pair of integers (Ai, Aj) satisfying Ai > Aj and i.
The idea is based on merge sort. When merge 2 sequences, A1, A2, …, Am and Am+1, Am+2, …, An, for each Ai>Aj (1<=i<=m and m+1<=j<=n), the counter of inversions add 1 to total value.
Begin Code:
int findInversion(vector* seq, int begin, int end, vector* newSeq) {
if(begin == end) {
(*newSeq)[0] = (*seq)[begin];
return 0;
}
int result = 0;
int middle = (begin+end)/2;
vector* left = new vector(middle - begin + 1);
vector* right= new vector(end - middle);
result = findInversion(seq,begin,middle,left) + findInversion(seq,middle+1,end,right);
//merge sequence left an sequence right
int iterLeft=0;
int iterRight=0;
int index=0;
while(iterLeftsize()){
if(iterRightsize() && (*left)[iterLeft]>(*right)[iterRight]){
(*newSeq)[index++] = (*right)[iterRight++];
result++;
}
else{
(*newSeq)[index++] = (*left)[iterLeft++];
}
}
while(iterRight <>size() ){
(*newSeq)[index++] = (*right)[iterRight++];
}
//release spaces and return
delete left,right;
return result;
}
End Code
Posted by sandun 
Sandun's Blog 
You must be logged in to post a comment.