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.