On Saturday, September 18, 2010, jagadish <jagadish1...@gmail.com> wrote:
> 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.
>
>
--
Ashish Kumar
Computer Science Engg.
CUSAT
+91 9995348620
--
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.
