bubble.py

def bubble_sort(l, inc=1):
    """Bubble Sort."""

    swapped = True
    while swapped:
        swapped = False
        for i in xrange(1, len(l)):
            if l[i - inc] > l[i] and i - inc >= 0:
                swapped = True
                l[i], l[i - inc] = l[i - inc], l[i]

from math import exp, sqrt

phi = 0.5 * (1.0 + sqrt(5.0))
ratio = 1.0 / (1.0 - exp(-phi))

def gaps(n):

    inc = n

    while True:
        inc = int(inc / ratio)
        if not inc:
            break
        yield inc


def comb_sort(l, steps=gaps):
    """Comb Sort."""

    for inc in steps(len(l)):
        bubble_sort(l, inc)