Counting number of inversion in an array (python)

def count_inversion(array):
    (count,sorted_array) = count_inversion_helper(array)
    return count

def count_inversion_helper(array1):
    """"
    counts the number for inversion in one array we assume the inversions
    are related to sorted array from
     0 to n (pep8 tested with 10.0 score)
    :author name: Tanmay Datta
    :param array1: array to count (list type)
    :return: number of inversoin
    :type array1: List(Num)
    """"
    length = len(array1)
    if length <= 1:
        #Trivial case and no inversion
        return (0, array1)
    if length == 2:
        if array1[0] &amp< array1[1]:
            return (0, array1)
        else:
            return (1, [array1[1], array1[0]]) # sorted array
    else:
        half = length/2
        right_array = array1[half:]
        (left_inversion, left_array) = count_inversion_helper(array1[:half])
        (right_inversion, right_array) = count_inversion_helper(array1[half:])
        sorted_array = []
        left_idx = 0
        right_idx = 0
        left_size = len(left_array)
        right_size = len(right_array)
        total_inversions = left_inversion + right_inversion
        while True:
            if right_array[right_idx] < left_array[left_idx]:
                sorted_array.append(right_array[right_idx])
                total_inversions += left_size - left_idx
                right_idx += 1

            else:
                sorted_array.append(left_array[left_idx])
                left_idx += 1
            if left_idx >= left_size:
                sorted_array += right_array[right_idx:]
                break
            if right_idx >= right_size:
                sorted_array += left_array[left_idx:]
                break
        return (total_inversions, sorted_array)

Another funky implementation which uses a “bisect” function already given by python libraries

import bisect

def ms_funky(arr):

sorted_array = sorted(arr)

r = 0

for n in arr:

    pos = bisect.bisect_left(sorted_array,n)

    r += pos

    sorted_array.pop(pos)

return r

Advertisements