Question

Can i please get help with problem 3? please, if possible, answer in a text format.

JN/2) f(n/2); f(n/2); f(n/2); Problem 3. Let A[O...n-1) be an array of n distinct integers. A pair (Ali), A[]) is said to be an inversion if these numbers are out of order, i.e., i<j but A[i] > AG). Design a O(n log n) time algorithm for counting the number of inversions.

Answer 1

#include<bits/stdc++.h>
using namespace std;
int merge(int a[],int st,int mid,int end)
{
int inv=0;
int temp[end-st+1];
int l=0;
int i=st;
int j=mid+1;
while(i<=mid && j<=end)
{
if(a[i]<a[j])
{
temp[l++]=a[i++];
}
else
{
temp[l++]=a[j++];
inv+=(mid-i+1);
}
}
while(i<=mid)
temp[l++]=a[i++];
while(j<=end)
temp[l++]=a[j++];
for(i=0;i<l;i++)
a[st+i]=temp[i];
return inv;
}
int countInversions(int a[],int st,int end)
{
int inv=0;
if(st<end)
{
int mid=(st+end)/2;
inv=countInversions(a,st,mid);
inv+=countInversions(a,mid+1,end);
inv+=merge(a,st,mid,end);
}
return inv;
}
int main()
{
int n,i;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
cout<<countInversions(a,0,n-1);
}

#include<bits/stdc++.h> using namespace std; int merge(int a[], int st, int mid, int end) int inv=0); int temp[end-st+1]; int l=0; int i=st; int j=mid+l; while(ic=mid && j<=end) if(a[i]<a[j]) { temp[1++]=a[i++]; else temp[l++]=a[j++]; inv+=(mid-i+1); while(i<=mid) temp[l++]=a[i++]; while(js=end) temp [l++]=a[j++]; for(i=0;i<l;i++) ast+i]=temp[i]; return inv; int countInversions(int all, int st, int end), int inv=0); if(st<end) int mid=(st+end)/2; inv=countInversions(a,st, mid); inv+=countInversions(a,mid+1, end); inv+=merge(a,st,mid, end); return inv; int main() int n,i; cin>>n; int a[n]; for(i=0;i<n;i++) cin>>a[i]; cout<<countInversions(a,0,n-1);

Input 5 4 3 2 1 Output

Time Complexity:- O(nlogn)

Please upvote if you found this solution useful and comment for any doubts.