You can count such pairs using the merge sort algorithm.
While in merge sort if at any place you need swapping then increase
the count.
here is the code
long long merge(long long *a,long long l,long long m,long long r)
{
long long i=l,j,k,t,c=0;
long long ml[MAX_SIZE];
long long n1=m-l+1;
j=l,k=m+1;
while(j<=m&&k<=r)
{
if(a[j]<=a[k])
ml[l]=a[j],l++,j++;
else{
ml[l]=a[k],k++;
c+=n1-j+i;
l++;
}
}
if(j>m)
for(t=k;t<=r;t++)
ml[t]=a[t];
else
for(t=j;t<=m;t++)
ml[l+t-j]=a[t];
for(j=i;j<=r;j++)
a[j]=ml[j];
return c;
}
long long mergesort(long long *a,long long l,long long r)
{
if(l>=r)
return 0;
long long m=(l+r)/2;
return mergesort(a,l,m) + mergesort(a,m+1,r) + merge(a,l,m,r);
}
On Jun 27, 11:32 am, Amit Jaspal <[email protected]> wrote:
> This is the famous Inversion Problem....
> Hint: you can do it in O(nlogn) using a tweek in merge sort
>
> On Sun, Jun 27, 2010 at 11:26 AM, Anil C R <[email protected]> wrote:
>
> > this is just brute force:
>
> > count = 0
> > for i in range(0, len(A)):
> > for j in range(i+1, len(A)):
> > if A[i] > A[j]:
> > count += 1
>
> > Time complexity = O(n**2)
> > Anil
>
> > On Sun, Jun 27, 2010 at 9:59 AM, sharad kumar
> > <[email protected]>wrote:
>
> >> Give an unsorted array find count of pairs of numbers[a,b] where a > b
> >> and b comes after a in the array.
>
> >> Eg. {8,3,6,10,5}
>
> >> the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected]<algogeeks%[email protected]>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%[email protected]>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
