Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.3 kB
1
Indexable
Never
def merge(arr, left, mid, right):
    i = left
    j = mid
    k = 0
    invCount = 0
    temp = [0 for x in range(right - left + 1)]

    while (i < mid) and (j <= right):
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            k += 1
            i += 1

        else:
            temp[k] = arr[j]
            invCount += mid - i
            k += 1
            j += 1

    while i < mid:
        temp[k] = arr[i]
        k += 1
        i += 1

    while j <= right:
        temp[k] = arr[j]
        k += 1
        j += 1

    k = 0
    for i in range(left, right + 1):
        arr[i] = temp[k]
        k += 1

    return invCount


def mergeSort(arr, left, right):
    invCount = 0

    if right > left:
        mid = (right + left) // 2

        invCount = mergeSort(arr, left, mid)
        invCount += mergeSort(arr, mid + 1, right)
        invCount += merge(arr, left, mid + 1, right)

    return invCount


def getInversions(arr, n):
    return mergeSort(arr, 0, n - 1)


def totle(n, A, k):
    arry = A.copy()
    t = getInversions(A, n)
    print(t)
    for i in range(0, n - k + 1):
        A = arry.copy()
        A[i:i + k] = A[i:i + k][::-1]
        # print(A, "arter inveri")
        t = min(getInversions(A, n), t)
        print(arry, A, t)
        A = arry
    return t