Inversion Count Efficient Code

In this class, We discuss Inversion Count Efficient Code.

The reader should have basic programming knowledge. Click Here for programming basics.

For Complete YouTube Video: Click Here

Inversion Count:

An array of n elements and count the number of inversions needed.

Count when a[i] > a[j] and i < j.

Example:

[3, 5, 1, 4, 6]

is 3> 5? no.

is 3 >1? yes. so the count increased. because a[i] > a[j] and i< j here i, and j are index positions of the elements.

Similarly, check the remaining possibilities and count.

Inversion count = 3

Example:

[8, 9, 10, 11]

Inversion count = 0

Conditions:

Time complexity is O(N log N)

Space complexity is O(n)

Solution:

We take merge sort logic to execute the code with given time complexity.

We place extra code to count the inversion in the merge sort code.

The you tube video will explain how to place the logic to do inversion count.

The time complexity of merge sort is O(N log N), and space complexity is O(n).

Below is the complete code.

^{inversion_count=0}   

^{def inversionCount(a,n):}

    ^{global inversion_count}

    ^{inversion_count = 0}

    ^{merge_sort(a, 0, n – 1)}

    ^{return inversion_count}

^{def merge(a, start, mid, end):}

    ^{global inversion_count}

    ^{temp = [0 for i in range(end – start + 1)]}  

    ^i=start

    ^{j=mid + 1}

    ^k=0    

    ^{while (i <= mid and j <= end):}

        ^{if (a[i] <= a[j]):}

            ^{temp[k] = a[i]}

            ^{k += 1}

            ^{i += 1}

        ^else:

            ^{temp[k] = a[j]}

            ^{k += 1}

            ^{j += 1}

            ^{inversion_count += mid – i + 1}

    ^{while (i <= mid):}

        ^{temp[k] = a[i]}

        ^{k += 1}

        ^{i += 1}

    ^{while (j <= end):}

        ^{temp[k] = a[j]}

        ^{k += 1}

        ^{j += 1}

    ^{for i in range(start, end + 1):}

        ^{a[i] = temp[i – start]}

^{def merge_sort(a,start,end):}  

    ^{if (start < end):}  

        ^{mid = (start + end) // 2}

        ^{merge_sort(a, start, mid)}  

        ^{merge_sort(a, mid + 1, end)}

        ^{merge(a, start, mid, end)}

^{n = int(input(‘enter the n value’))}

^{print(“enter the n elements”)}

^a=[]

^{for i in range(n):}

    ^{x = int(input())}

    ^a.append(x)

^{z = inversionCount(a,n)}

^{print(‘output:’,z)}