Hello,
Here is the code :
#include<stdio.h>
int mergeandcountinversion(int a[],int begin,int middle,int end,int z)
{
int length=end-begin+1;
int tmp[length];
int i1=begin,i2=middle+1,it=0,i=0;
for(i=0;i<length;i++)
{
if(i1>middle)
{
for(;i2<=end;i2++)
{
tmp[it]=a[i2];
it++;
}
break;
}
if(i2>end)
{
for(;i1<=middle;i1++)
{
tmp[it]=a[i1];
it++;
}
break;
}
if(a[i1]<=a[i2])
{
tmp[it]=a[i1];
it++;
i1++;
}
else if(a[i2]<a[i1])
{
tmp[it]=a[i2];
it++;
i2++;
z+=middle-i1+1;
}
}
i1=begin;
for(i=0;i<length;i++)
{
a[i1++]=tmp[i];
}
return z;
}
int m_sort(int a[],int begin,int end)
{
int middle=(begin+end)/2,x=0,y=0;
if(begin==end)
return 0;
x=m_sort(a,begin,middle);
y=m_sort(a,middle+1,end);
return x+y+mergeandcountinversion(a,begin,middle,end,0);
}
int mergesort(int a[],int n)
{
return m_sort(a,0,n-1);
}
int main()
{
int a[]={4,5,3,1,2};
int n=5,i=0;
printf("%d\n",mergesort(a,n));
}
Thanks & Regards,
Anantha Krishnan
On Thu, Jun 9, 2011 at 4:54 PM, Navneet Gupta <[email protected]> wrote:
> Ohh. Missed out the nlogn condition you mentioned. It will do but in n^2
>
> Sent from my Windows Phone
> ------------------------------
> From: D.N.Vishwakarma@IITR
> Sent: Thursday, 9 June 2011 4:29 PM
> To: [email protected]
> Subject: Re: [algogeeks] Finding total number of inversions in an array in
> O(nlogn) complexity .
>
> how insertion sort will do in O(nlogn)?
>
> On Thu, Jun 9, 2011 at 4:27 PM, Navneet Gupta <[email protected]>wrote:
>
>> Insertion sort also would do.
>>
>> On Thu, Jun 9, 2011 at 4:22 PM, D.N.Vishwakarma@IITR <[email protected]>
>> wrote:
>> > thanx for suggestion
>> >
>> > On Thu, Jun 9, 2011 at 4:08 PM, sunny agrawal <[email protected]>
>> > wrote:
>> >>
>> >> Discussed many times,
>> >> 1) add some lines to merge sort
>> >> 2) use Binary indexed tree for a faster version (i have not tried but
>> get
>> >> to know it can be done using binary indexed tree)
>> >>
>> >> On Thu, Jun 9, 2011 at 4:05 PM, D.N.Vishwakarma@IITR <
>> [email protected]>
>> >> wrote:
>> >>>
>> >>> Inversion means pair(i,j) such that i<j and A[i]>A[j]
>> >>>
>> >>> --
>> >>> With Regards
>> >>> Deoki Nandan Vishwakarma
>> >>> IITR MCA
>> >>>
>> >>>
>> >>> --
>> >>> 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.
>> >>
>> >>
>> >>
>> >> --
>> >> Sunny Aggrawal
>> >> B-Tech IV year,CSI
>> >> Indian Institute Of Technology,Roorkee
>> >>
>> >> --
>> >> 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.
>> >
>> >
>> >
>> > --
>> > With Regards
>> > Deoki Nandan Vishwakarma
>> > IITR MCA
>> >
>> >
>> > --
>> > 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.
>> >
>>
>>
>>
>> --
>> --Navneet
>>
>> --
>> 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.
>>
>>
>
>
> --
> **With Regards
> Deoki Nandan Vishwakarma
> IITR MCA
> *
> *
>
> --
> 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.
>
> --
> 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.
>
--
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.
