In [3]:

    

from resources.utils import run_tests


    

In [23]:

    

def counting_inversions_n_squared(array):
    count = 0
    
    # O(N ** 2)
    for i in range(len(array)):
        for j in range(i, len(array)):
            if array[i] > array[j]:
                count += 1
                
    return count


    

In [27]:

    

tests = [
    (dict(array=[1, 2, 3, 4, 5]), 0),
    (dict(array=[1, 2, 3]), 0),
    (dict(array=range(1000)), 0),
    (dict(array=[2, 1]), 1),
    (dict(array=[3, 2, 1]), 3),
    (dict(array=range(3)[::-1]), 3),
    (dict(array=range(4)[::-1]), 6),
    (dict(array=range(10)[::-1]), 10 * 9 / 2),
    (dict(array=range(100)[::-1]), 100 * 99 / 2),
    (dict(array=[1, 3, 5, 2, 4, 6]), 3)
]


    

In [28]:

    

run_tests(tests, counting_inversions_n_squared)


    

    




✓ All tests successful

In [29]:

    

5 / 2


    

    
Out[29]:





2.5

In [82]:

    

def counting_inversions(array):
    
    def _combine(left, right):
        output = []
        pointer_left = 0
        pointer_right = 0
        
        while True:
            if pointer_left == len(left):
                output += right[pointer_right:]
                
                if pointer_right < len(right) - 1:
                    print('+1')
                
                break
            elif pointer_right == len(right):
                print('+1')
#                 for _ in range(len(left) - pointer_left):
#                     print(len(left), pointer_left)
#                     print('+1XXX')
                output += left[pointer_left:]
                break
            
            if left[pointer_left] < right[pointer_right]:
                output.append(left[pointer_left])
                pointer_left += 1
            else:
                output.append(right[pointer_right])
                print('+1X')
                pointer_right += 1
            
        return output
    
    if len(array) <= 1:
        return array
    else:
        mid_point = int(len(array) / 2)
        count_left = counting_inversions(array[:mid_point])
        count_right = counting_inversions(array[mid_point:])
        # count_split = ???
        
        return _combine(counting_inversions(count_left), counting_inversions(count_right))


    

In [83]:

    

counting_inversions(**tests[-1][0])


    

    




+1
+1
+1
+1
+1X
+1X






    
Out[83]:





[1, 2, 3, 4, 5, 6]

In [ ]: