Homework-1/qsort.py

def qsort(xs):
    if xs == []: return []

    pivot = xs[0]
    left = [x for x in xs if x < pivot]
    right = [x for x in xs[1:] if x >= pivot]
    return [qsort(left)] + [pivot] + [qsort(right)]

def _sorted(tree, acc):
    if tree == []: return

    _sorted(tree[0], acc)
    acc.append(tree[1])
    _sorted(tree[2], acc)

def sorted(tree):
    acc = []
    _sorted(tree, acc)
    return acc

def search(tree, x):
    return _search(tree, x) != []

def insert(tree, x):
    node = _search(tree, x)
    if node == []:
        node.append([])
        node.append(x)
        node.append([])

def _search(tree, i):
    if tree == []: return tree

    pivot = tree[1]
    if pivot == i: return tree
    elif i < pivot: return _search(tree[0], i)
    else: return _search(tree[2], i)