Counting inversions of an array using DAC approach

Question

I'm trying to code to count the inversions of an array using DAC approach. Below is the code I'm using in Python

arr=[1,3,5,2,4,6]
n=6
l=0
h=n-1
count=0

def inversions(l,h):
    if(l==h):
        return [arr[l]]

    m=(h+l)//2
    arr1=inversions(l,m)
    arr2=inversions(m+1,h)

    s1=m-l
    s2=h-(m+1)
    mer=[]
    k1=k2=0

    while(k1<=s1 and k2<=s2):
        if(arr1[k1] < arr2[k2]):
            mer.append(arr1[k1])
            k1+=1
        else:
            count+=(k2-(m+1))
            mer.append(arr2[k2])
            k2+=1

    if(k1>s1):
        mer.extend(arr2[k2:s2+1])

    if(k2>s2):
        mer.extend(arr2[k1:s1+1])    

    return mer

res=inversions(l,h)

print('Total No. of Inversions : %d' %count)

On running the above code I'm getting this error message.

UnboundLocalError: local variable 'count' referenced before assignment

I am not able to understand this error. Can anybody tell me why I'm geting this error?

Answer 1

Look at your code at line 26.

arr1 = inversions(l, m)

In this line, you are assigning the value that your function returns. But what your function actually returns? Then think, what type of content your list contains? Definitely, 'Nonetype'.

Then see the line,

if(arr1[k1] > arr2[k2]):

You are comparing i.e try to substracting two Nonetype object, that's why the error.

The error is occurring because you are trying to assign value to a variable before declaring it. You may tell that, well, i have declared it outside the function. If you want to use the global one, you have to tell explicitly to do so, unless it will consider it as a local variable to the function.

To solve your recent error, you can use the following line just before you assigned value to count in your function.

global count

But, i don't think you have written your code perfectly. There is still bug on it. Hope you will fix it yourself :)

This is running perfectly on my machine, though with wrong output.

def inversions(l,h):

    if(l==h):
        return [arr[l]]

    m=(h+l)//2
    arr1=inversions(l,m)
    arr2=inversions(m+1,h)

    s1=m-l
    s2=h-(m+1)
    mer=[]
    k1=k2=0

    while(k1<=s1 and k2<=s2):
        if(arr1[k1] < arr2[k2]):
            mer.append(arr1[k1])
            k1+=1

        else:
            global count
            count +=(k2-(m+1))
            mer.append(arr2[k2])
            k2+=1

    if(k1>s1):
        mer.extend(arr2[k2:s2+1])

    if(k2>s2):
        mer.extend(arr2[k1:s1+1])

    return mer

res=inversions(l,h)

print('Total No. of Inversions : %d' %count)