Hi Raj,
I think there is an nlogn solution to this problem which can be done
by modifying merge sort..
the key lies in the merge routine, when the left array elements are
greater than the right array,
the right array elements are copied to the tmp array .. hence , this
adds (n-i) to the inversion count.!
the code is below--
int mergesort(int arr[],int l,int r) {
if(l<=r) {
mid=l+r/2;
return mergesort(arr,l,mid)+mergesort(arr,mid+1,r)
+merge(a,tmp,l,mid,r);
}
}
int merge(int a[],int t[],int lpos,int rpos,int rend) {
lend=rpos-1;
while(lpos<=lend && rpos<=rend) {
if(arr[lpos]<=arr[rppos] arr[tmppos++]=arr[lpos++ //dont update any
count here,, no inversions
else {
//we have an inversion and elements from (lend-lpos) are inverted
inversioncount+=lend-lpos;
arr[tmppos++]=arr[rpos++]
}
if(lpos==lend) { copy from rpos to rend to tmp array }
else {copy from lpos to lend to tmp array} //usual mergesort thingy
RETURN inversioncount;
}
}
On Sep 13, 7:40 pm, Raj N <rajn...@gmail.com> wrote:
> Given an array of n integers find all the inversion pairs in O(n)
> Inversion pair is one where a[i]>a[j], i<j
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
