Algos

algo.py

import math

def selection_sort(a):
    for i in range(len(a)):
        curr_min = i
        for j in range(i, len(a)):
            if a[j] < a[curr_min]:
                curr_min = j
        if curr_min != i:
            a[i], a[curr_min] = a[curr_min], a[i]
    return a

    
def insertion_sort(a):
    for i in range(len(a)):
        curr = i
        while (curr > 0) and (a[curr] < a[curr-1]):
            a[curr], a[curr-1] = a[curr-1], a[curr]
            curr -= 1
    return a
    
    
def merge_sort(a):
    if len(a) == 1:
        return a
    left = a[:math.floor(len(a)/2)]
    right = a[math.floor(len(a)/2):]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)
    
def merge(l, r):
    merged = []
    while (len(l) > 0) and (len(r) > 0):
        if l[0] > r[0]:
            merged.append(r[0])
            r.pop(0)
        else:
            merged.append(l[0])
            l.pop(0)
    while len(l) > 0:
        merged.append(l[0])
        l.pop(0)
    while len(r) > 0:
        merged.append(r[0])
        r.pop(0)
    return merged


def binary_search(a, val, start, stop):
    if start >= stop:
        return None
    middle = math.floor((start+stop)/2)
    if a[middle] == val:
        return middle
    elif a[middle] > val:
        return binary_search(a, val, start, middle)
    elif a[middle] < val:
        return binary_search(a, val, middle+1, stop)



a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]


print(selection_sort(a))
print(insertion_sort(a))
print(merge_sort(a))
print(binary_search(merge_sort(a), 10, 0, len(a)))