al.py

def insert_sort(A, reverse=False):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1


        # Insert A[j] to sorted sequence of A[:j]
        if reverse:
            while i >= 0 and A[i] < key:
                A[i+1] = A[i]
                i -= 1
        else:
            while i >= 0 and A[i] > key:
                A[i+1] = A[i]
                i -= 1
        A[i+1] = key

    return A


def merge(A, p, q, r):
    L = A[p:q] + [float('inf')]
    R = A[q:r] + [float('inf')]

    i, j = 0, 0
    for k in range(p, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def merge_sort(A, p, r):
    if p < r:
        q = (p + r) // 2
        if q == p:
            merge(A, p, p+1, r+1)
        else:
            merge_sort(A, p, q)
            merge_sort(A, q, r)
            merge(A, p, q, r)
    return A



def find_maximum_cross_subarray(A, low, mid, high):
    left_sum = - float('inf')
    sum_ = 0
    for i in range(mid, low-1, -1):
        sum_ += A[i]
        if sum_ > left_sum:
            left_sum = sum_
            max_left = i
    
    right_sum = - float('inf')
    sum_ = 0
    for j in range(mid+1, high+1):
        sum_ += A[j]
        if sum_ > right_sum:
            right_sum = sum_
            max_right = j
    
    return max_left, max_right, left_sum + right_sum


def find_maximum_subarray(A, low, high):
    if high == low:
        return low, high, A[low]
    
    else:
        mid = (low + high) // 2
        left_low, left_high, left_sum = find_maximum_subarray(A, low, mid)
        right_low, right_high, right_sum = find_maximum_subarray(A, mid+1, high)
        cross_low, cross_high, cross_sum = find_maximum_cross_subarray(A, low, mid, high)
    
    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_low, left_high, left_sum
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_low, right_high, right_sum
    else:
        return cross_low, cross_high, cross_sum


def max_heapify(A, i, till):
    l = 2*i
    r = 2*i + 1

    if l < till and A[l] < A[i]:
        largest = l
    else:
        largest = i
    
    if r < till and A[r] < A[largest]:
        largest = r
    
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest, till)

    return A



def heap_sort(A):
    # Build Heap Tree
    for i in range(len(A) // 2, -1, -1):
        max_heapify(A, i, len(A))
    print(A)

    # Left every element flow from top to correct postion
    for i in range(len(A)-1, 0, -1):
        A[0], A[i] = A[i], A[0]
        A = max_heapify(A, 0, i)
    return A

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        print(p, q, r, A)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)


class Node:
    def __init__(self, left=None, right=None, parent=None, key=None):
        self.left = left
        self.right = right
        self.parent = parent
        self.key = key

def in_order_tree_walk(x:Node):
    if x != None:
        in_order_tree_walk(x.left)
        print(x.key)
        in_order_tree_walk(x.right)

def tree_search(x, k):
    if x == None or k == x.key:
        return x
    if k < x.key:
        return tree_search(x.left, k)
    if k > x.key:
        return tree_search(x.right, k)

def iterative_tree_search(x, k):
    while x is not None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x

def tree_min(x):
    while x.left is not None:
        x = x.left
    return x

def tree_max(x):
    while x.right is not None:
        x = x.right
    return x

def tree_succ(x):
    if x.right is not None:
        return tree_min(x.right)
    
    y = x.parent
    while y is not None and x == y.right:
        x = y
        y = y.parent
    return y

def tree_prec(x):
    if x.left is not None:
        return tree_max(x.left)
    
    y = x.parent
    while y is not None and x == y.left:
        x = y
        y = y.parent
    return y


if __name__ == '__main__':
    A = [5, 2, 4, 6, 1, 3, 8, 7]
    print("=============")
    print(f"Before Sort: {A}")
    reverse = True
    # B = insert_sort(A, reverse)
    B = merge_sort(A, 0, len(A)-1)
    print(f"After Sort: {B}\t")

    A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, -15, -4, 7]
    print(f"Price Change {A}")
    print(find_maximum_subarray(A, 0, len(A)-1))

    A = [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]
    print(heap_sort(A))

    A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, -15, -4, 7]
    quick_sort(A, 0, len(A)-1)