(Counting inversions) An inversion in an array Al1... n] of numbers is a pair of
ID: 3754983 • Letter: #
Question
(Counting inversions) An inversion in an array Al1... n] of numbers is a pair of indices (i, j such that i Alil In other words, an inversion describes a pair of elements that are not in sorted order. a. Find an array of length n over the elements (1, ., n that maximizes the number of inversions and explain why it is optimal. By modifying Merge Sort, design an algorithm that counts the number of inversions in an array of length n in 0(n lg n) time. (Note: There can be 0(n) inversions in an n-element array, so your algorithm cannot explicitly list them and achieve the time bound. It is possible to count inversions without listing them.) b.Explanation / Answer
a)
Answer:
array which is descending order
explanation:
given that inversion is pair of indices where i<j and A[i]>A[j]
now, to maximize the number of inversions
every pair of i and j where i<j
must have A[i]>A[j]
this is only possible when list is in descending order
hence, it has optimal inversions
b)
Answer:
MergeSort(int A[], int Temp], int Left, int Right)
{
int Mid, Inversions_count = 0;
if (Right > Left)
{
Mid = (Right + Left)/2;
Inversions_count = MergeSort(A, temp, Left, Mid); //inversion count from left
Inversions_count += MergeSort(A, temp, Mid+1, Right); //inversion count from right
Inversions_count += Merge(A, temp, Left, Mid+1, Right); //inversion count after mering
}
return Inversions_count; //retunring inversion count
}
Merge(int A[], int Temp], int Left, int Mid, int Right)
{
int i, j, k;
int Inversions_count = 0; //intializing
i = Left;
j = Mid;
k = Left;
while ((i <= Mid - 1) && (j <= Right))
{
if (A[i] <= A[j])
{
Tempk++] = A[i++];
}
else
{
Tempk++] = A[j++];
//modified here
//to find inversion count
Inversions_count = Inversions_count + (Mid - i);
}
}
while (i <= Mid - 1)
Tempk++] = A[i++];
while (j <= Right)
Tempk++] = A[j++];
for (i=Left; i <= Right; i++)
A[i] = Tempi];
return Inversions_count; //returning inversion count
}
//if you find this helpful pls give a thumbsup, thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.