[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

Advertisements