CLRS Solutions | Problem 2-4

Inversions

Let $A[1 \ldots n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$.

List the five inversions of the array $\langle 2, 3, 8, 6, 1 \rangle$.

What array with elements from the set $\{1, 2, \ldots , n\}$ has the most inversions? How many does it have?

What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta(n \lg n)$ worst-case time. (Hint: Modify merge sort.)

A. List of Inversions

Inversions in the given array are: (1, 5), (2, 5), (3, 4), (3, 5), and (4, 5). (Note: Inversions are specified by indices of the array, not by values.)

B. Array With Most Inversions

The array with elements from the set ${1, 2, \dots , n}$ with the most inversions will have the elements in reverse sorted order, i.e. $\langle n, n - 1, \dots, 2, 1 \rangle$.

As the array has $n$ unique elements in reverse sorted order, for every unique pair of $(i, j)$, there will be an inversion. So, total number of inversion = number of ways to choose 2 distinct integer from the set ${1, 2, \dots , n}$ = $^nC_2$ = $\frac {n( n - 1)} 2$.

Another way to find number of inversions in such an array, is to notice that there will be $n - 1$ inversions with the first index as the first element of the inversion pair, $n -2$ inversions with the second index as the first element of the inversion pair, and so on. And finally, zero inversions with the $n$-th index as the first element of the inversion pair.

In other words, total number of inversions = $(n - 1) + (n - 2) + \cdots + 1 = \frac {n(n -1 )} 2$.

C. Relationship With Insertion Sort

If we take a look at the pseudocode for insertion sort with the definition of inversions in mind, we will realize that more the number of inversions in an array, the more times the inner while loop will run.

This is also in line with our findings in sub-problem b. Maximum number of inversions are possible when the array is reverse sorted.

So, the higher the number of inversions in an array, the longer insertion sort will take to sort the array.

D. Algorithm to Calculate Inversions

Although a hint to modify merge sort is already given, without that also we should think of divide-and-conquer algorithms whenever we see running time with $\lg n$ term.

As was done in merge sort, we need to recursively divide the array into halves and count number of inversions in the sub-arrays. This will result in $\lg n$ steps and $\Theta(n)$ operations in each step to count the inversions. All in all a $\Theta(n \lg n)$ algorithm.

The problem did not specifically asked to write pseudocode, but we can do that as well for the sake of completion.

We can rewrite $\textsc {Merge-Sort}$ as follows to repeatedly subdivide the array and count number of inversions in each half.

$$\textsc {Count-Inversions }(A, p, r)$$$$\begin{aligned}1& \quad \textbf {if }p\geq\,\,r \\2& \quad \qquad \textbf {return }0 \\3& \quad q=\lfloor \textsc {}(p+r)/2\rfloor \\4& \quad left=\textsc {Count-Inversions}(A,\,p,\,q) \\5& \quad right=\textsc {Count-Inversions}(A,\,q+1,\,r) \\6& \quad inversions=left+right+\textsc {Merge}(A,\,p,\,q,\,r) \\7& \quad \textbf {return }inversions \\\end{aligned}$$

And here is the modified $\textsc {Merge-Sort}$ pseudocode that actually counts the number of inversion in linear time.

$$\textsc {Merge }(A, p, p, r)$$$$\begin{aligned}1& \quad n_{1}=q-p+1 \\2& \quad n_{2}=r-q \\3& \quad \text {let }L[1..n_{1]}\text { and }R[1..n_{2]}\text { be }\text { new }\text { arrays } \\4& \quad \textbf {for }i=1\textbf { to }n_{1} \\5& \quad \qquad L[i]=A[p+i-1] \\6& \quad \textbf {for }j=1\textbf { to }n_{2} \\7& \quad \qquad R[j]=A[q+j] \\8& \quad L[n_{1}+1]=\infty \\9& \quad R[n_{2}+1]=\infty \\10& \quad i=1 \\11& \quad j=1 \\12& \quad inversions=0 \\13& \quad \textbf {for }k=p\textbf { to }r \\14& \quad \qquad \textbf {if }L[i]\leq\,\,R[j] \\15& \quad \qquad \qquad A[k]=L[i] \\16& \quad \qquad \qquad i=i+1 \\17& \quad \qquad \textbf {else } \\18& \quad \qquad \qquad inversions=inversions+\textsc {}(n_{1}-i+1) \\19& \quad \qquad \qquad A[k]=R[j] \\20& \quad \qquad \qquad j=j+1 \\21& \quad \textbf {return }inversions \\\end{aligned}$$