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)
            return (1, [array1[1], array1[0]]) # sorted array
        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]:
                total_inversions += left_size - left_idx
                right_idx += 1

                left_idx += 1
            if left_idx >= left_size:
                sorted_array += right_array[right_idx:]
            if right_idx >= right_size:
                sorted_array += left_array[left_idx:]
        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


return r


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.