Yossarian0916

from math import floor, ceil
"""
implement Karatsuba algorithm O(n ** log3)
"""


# karatsuba multiplication
def karatsuba(a, b, base=10):
    """
    divide each number into two halves, the high bits H and the low bits L

Yossarian0916

"""
how many girls should one date before he can be in a relationship with 
all 12 zodiac signs
"""
import random


def simulation():
    count = 0
    gf = set()

Yossarian0916

"""
compute the number of inversions of the given array
running time is O(nlogn)
using divide and conquer
"""

def count_split_inv(array, left, right):
    count = 0
    i, j = 0, 0
    length = len(left) + len(right)

Yossarian0916

import random


def partition(array, l, r):
    pivot = array[l]  # choose the 1st element as the pivot
    i = l+1
    for j in range(l+1, r):
        if array[j] < pivot:
            array[j], array[i] = array[i], array[j]
            i += 1

Yossarian0916

def merge_sort(array):
    if len(array) == 1:
        return array
    else:
        mid = len(array) // 2
        left = merge_sort(array[:mid])
        right = merge_sort(array[mid:])
    return merge(left, right)

Yossarian0916

from collections import defaultdict


class PriorityQueue:
    """
    each heap element is in form (key value, object handle), while heap
    operations works based on comparing key value and object handle points to
    the corresponding application object.
    """