stanford-algo-week-1.py

import math

array = [] # 2407905288
three = [2, 4, 1, 3, 5]
five = [1, 20, 6, 4, 5]

with open('./IntegerArray.txt') as f:
    for line in f:
        array.append(int(line))

def brute_force(array):
    inversions = 0
    for o in range(0, len(array) - 1):
        for i in range(o + 1, len(array)):
            if array[o] > array[i]:
                inversions += 1
    return inversions

#print(brute_force(three))
#print(brute_force(five))
#print(brute_force(array))

def sort_and_count(array):
    if len(array) == 1:
        return [array, 0]
    else:
        half = int(math.floor(len(array) / 2))
        b, x = sort_and_count(array[:half])
        c, y = sort_and_count(array[half:])
        d, z = merge_and_count_split_inversion(b, c)
        return [d, (x + y + z)]

def merge_and_count_split_inversion(b, c):
    inversions = 0
    d = []
    i = 0
    j = 0
    while i < len(b) and j < len(c):
        print(b[i], c[j])
        if b[i] < c[j]:
            d.append(b[i])
            i = i + 1
        else:
            d.append(c[j])
            j = j + 1
            inversions = inversions + 1
    while i < len(b):
        d.append(b[i])
        i = i + 1
    while j < len(c):
        d.append(c[j])
        j = j + 1
    return [d, inversions]

print(sort_and_count(three))
#print(sort_and_count(five))
#print(sort_and_count(array)[1])