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 <iit2007...@iiita.ac.in> 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 <cr.a...@gmail.com> 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
> > <sharad20073...@gmail.com>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 algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> >> .
> >> 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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > 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 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.
