Quick sort

def qsort(seq):
    pivot= seq[0]
    def lt(x): return x < pivot
    def gt(x): return x > pivot
    return qsort( filter( lt, seq[1:])) + [pivot] + qsort( filter( gt, seq[1:]))

Find n largest/ smallest item in a list

Using python built-in heapq functions:

def find_nsmallest( seq, n):
    import heapq
    return heapq.nsmallest( n, seq)

def find_nlargest( seq, n):
    import heapq
    return heapq.nlargest( n, seq)

Recursive-definition:

def nlargest( seq, n):
    pivot= seq[0]
    below= [s for s in seq if s < pivot]
    above= [s for s in seq if s > pivot]
    i,j= len( below), len( seq) - len(above)
    
    if n < i: return nlargest( below, n)
    elif n >= j: return nlargest( above, n-j)
    else: return pivot

Binary Search

def binary_search( seq, n):
    low, high= 0, len(seq)-1
    while low <= high:
        mid= (low + high)/2;
        if n == seq[mid]:
            return True
        elif n < seq[mid]:
            high= mid -1
        elif n > seq[mid]:
            low= mid +1
    return False


if __name__ == "__main__":
    seq= [1,5,9,12,18,35]
    print binary_search( seq, 15)

Fibonacci numbers

Recursive definition:

def fibo(n):
    if n == 0: return 0
    if n == 1: return 1
    if n == 2: return 1
    return fibo(n-1) + fibo(n-2)

def fibonacci(n):
    result= []
    a,b= 0,1
    while a < n:
        result.append(a)
        a,b= b, a+b
    return result

Complete:

def fibo(n):
    if n == 0: return 0
    if n == 1: return 1
    if n == 2: return 1
    return fibo(n-1) + fibo(n-2)


def fibonacci(n):
    result= []
    a,b= 0,1
    while a < n:
        result.append(a)
        a,b= b, a+b
    return result

if __name__ == '__main__':
    print fibo(5000)


[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Factorial

Version1:
Recursive version

def factorial(n):
    if n == 0: return 0
    if n == 1: return 1
    if n > 2:
        return n * factorial(n-1)

Memoization of factorial function:

mem= {}
def factorial(n):
    if n == 0: return 0
    if n == 1: return 1
    if n > 2:
        mem[n] = n * factorial( n-1)
    return mem