2-4 Inversions

Let $A[1: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.

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

b. What array with elements from the set $\langle 1,2,\dots ,n \rangle$. has the most inversions? How many does it have?

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

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

• a. (1,5),(2,5),(3,4),(3,5),(4,5)

• b. $\langle n,n-1,\dots ,1\rangle \text{ totally has } {n \choose 2} = n(n-1)/2 \text{ inversions}$

• c. The running time of insertsion sort is a constant times the number of inversions, since each time exchanging elements in insertion sort reduces Inversions num by 1.

• d.

MERGE_INVERSIONS (A,l,r,mid)
    inversions = 0
    n1 = mid - l
    n2 = r - mid -1
    L[0:n1]
    for i = 0 to n1
        L[i] = A[l + i]
    R[0:n2]
    for j = 0 to n2
        R[j] = A[mid + 1 + j]
    i=0 
    j=0
    k=l
    while i <= n1 and j <= n2
        if L[i] <= R[j]
            A[k] = L[i]
            i++
            k++
        else
            A[k] = R[j]
            j++
            k++
            inversions + = n1 - i + 1
    while i <= n1
        A[k] = L[i]
        k++
        i++
    while j <= n2
        A[k] = R[j]
        k++
        j++
MERGE_SORT_INVERSIONS(A,l,r)
    inversions = 0
    if l >=r
        return inversions
    mid = floor((l+r)/2)
    inversions + = MERGE_SORT_INVERSIONS(A,l,mid)
    inversions + = MERGE_SORT_INVERSIONS(A,mid+1,r)
    inversions + = MERGE_INVERSIONS(A,l,mid,r)
    return inversions