Python Algorithms

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def binary_search(array, target):
    lower, upper = 0, len(array)
    while lower < upper:
        mid = lower + (upper - lower) // 2
        val = array[mid]
        if target == val:
            return mid
        elif target > val:
            if lower == mid:
                break
            lower = mid
        elif target < val:
            upper = mid

1
2
3
4
5
6
7
8

def insertion_sort(seq):
    for j in range(1, len(seq)):
        key = seq[j]
        i = j - 1
        while i > 0 and seq[i] > key:
            seq[i+i] = seq[i]
            i -= 1
        seq[i+1] = key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def mergesort(seq):
    mid = len(seq) // 2
    lft, rgt = seq[:mid], seq[mid:]
    if len(lft) > 1:
        lft = mergesort(lft)
    if len(rgt) > 1:
        rgt = mergesort(rgt)
    res = []
    while lft and rgt:
        if lft[-1] < rgt[-1]:
            res.append(lft.pop())
        else:
            res.append(rgt.pop())
    res.reverse()
    return (lft or rgt) + res

1
2
3
4
5

def bubble_sort(seq):
    for i in range(0, len(seq)-2):
        for j in range(len(seq) - 1, i + 1, -1):
            if seq[j] < seq[j-1]
                seq[j], seq[j-1] = seq[j-1], seq[j]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def swap(j, j):
    seq[i], seq[j] = seq[j], seq[i]
def heapify(end, i):
    lft = 2 * i + 1
    rgt = 2 * (i + 1)
    max = i
    if lft < end and seq[i] < seq[lft]:
        max = lft
    if rgt < end and seq[max < seq[rgt]:
        max = rgt
    if max != i:
    	swap(i, max)
        heapify(end, max)
def heap_sort():
    end = len(seq)
    start = end // 2 - 1
    for i in range(start, -1, -1):
        heapify(end, i)
    for i in range(end-1, 0, -1):
        swap(i, 0)
        heapify(i, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def partition(seq):
    pivot, seq = seq[0], seq[1:]
    left = [x for x in seq if x <= pivot]
    right = [x for x in seq if x > pivot]
    return left, pivot, right
def quicksort(seq):
    if len(seq) <= 1:
        return seq
    left, pivot, right = partition(seq)
    return quicksort(left) + [pivot] + quicksort(right)

1
2
3
4
5
6
7
8

from collections import defaultdict
def counting_sort(A, key=lambda x : x):
    B, C = [], defaultdict(list)
    for x in A:
        C[key(x)].append(x)
    for k in range(min(C), max(C)+1):
        B.extend(C[k])
    return B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Node:
    lft = None
    rgt = None
    def __init__(self, key, val):
        self.key = key
        self.val = val
        
def insert(node, key, val):
    if node is None: 
    	return Node(key, val)
    if node.key == key: 
    	node.val = val
    elif key < node.key:
        node.lft = insert(node.lft, key, val)
    else:
        node.rgt = insert(node.rgt, key, val)
    return node
    
def search(node, key):
    if node is None: 
        raise KeyError
    if node.key == key: 
        return node.val
    elif key < node.key:
        return search(node.lft, key)
    else:
        return search(node.rgt, key)
        
class Tree:
    root = None
    def __setitem__(self, key, val):
        self.root = insert(self.root, key, val)
    def __getitem__(self, key):
        return search(self.root, key)
    def __contains__(self, key):
        try:
            seach(self.root, key)
        except KeyError:
            return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def bfs(G, s):
    P, Q = {s: None}, deque([s])
    while Q:
        u = Q.popleft()
        for v in G[u]:
            if v in P:
                continue
            p[v] = u
            Q.append(v)
    return P

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def rec_dfs(G, s, S=None):
    if S is None: S = set()
    S.add(s)
    for u in G[s]:
        if u in S:
            continue
        rec_dfs(G, u, S)

def iter_dfs(G, s):
    S, Q = set(), []
    Q.append(s)
    while Q:
        u = Q.pop()
    if u in S:
        continue
    S.add(u)
    Q.extend(G[u])
    yield u