A bit of code kata for me. Brushing back up on some sorting algorithms... Requires ``pip install chrono`` to run.

gistfile1.txt

Total time for 500 runs.

Bubble sort [average]: 0.00372815132141 seconds
Bubble sort [worst]: 0.00349998474121 seconds
Bubble sort [best]: 0.00349807739258 seconds
Bubble sort [huge]: 6.59933185577 seconds

Quick sort [average]: 0.00668597221375 seconds
Quick sort [worst]: 0.0066499710083 seconds
Quick sort [best]: 0.00685095787048 seconds
Quick sort [huge]: 0.763675928116 seconds

Insertion sort [average]: 0.00117206573486 seconds
Insertion sort [worst]: 0.00106191635132 seconds
Insertion sort [best]: 0.00106120109558 seconds
Insertion sort [huge]: 0.0531949996948 seconds

Python sort [average]: 0.000449895858765 seconds
Python sort [worst]: 0.000391960144043 seconds
Python sort [best]: 0.000391006469727 seconds
Python sort [huge]: 0.00664901733398 seconds

outofsorts.py

from __future__ import print_function
import math


def bubble_sort(values):
    vlen = len(values)

    for i in range(vlen - 1, 0, -1):
        for j in range(0, i):
            if values[j] > values[j + 1]:
                # Swap them.
                values[j + 1], values[j] = values[j], values[j + 1]

    return values


def quick_sort(values):
    # If it's 1 or zero in length, it's sorted.
    if len(values) <= 1:
        return values

    # Find the halfway mark, divide & conquer!
    vlen = len(values)
    midway = int(math.ceil(len(values) / 2.0))
    pivot = values[midway]
    lesser = []
    greater = []

    for i in range(vlen):
        if i == midway:
            # Skip the pivot.
            continue

        if values[i] <= pivot:
            lesser.append(values[i])
        else:
            greater.append(values[i])

    return quick_sort(lesser) + [pivot] + quick_sort(greater)


def insertion_sort(values):
    vlen = len(values)

    for i in range(1, vlen):
        offset = i
        value = values[i]

        while offset > 0 and value < values[offset - 1]:
            values[offset] = values[offset - 1]
            offset -= 1

        values[offset] = value

    return values


if __name__ == '__main__':
    import random
    import chrono

    runs = 500
    average = [5, 7, 21, 1, 4, 2, 19, 10]
    sorted_average = sorted(average)
    worst = [21, 19, 10, 7, 5, 4, 2, 1]
    sorted_worst = sorted(worst)
    best = [1, 2, 4, 5, 7, 10, 19, 21]
    sorted_best = sorted(best)
    huge = [random.randint(0, 1000) for i in range(501)]
    sorted_huge = sorted(huge)

    print("Total time for {0} runs.".format(runs))
    print()

    with chrono.Timer() as average_bubble:
        for i in range(runs):
            assert bubble_sort(average) == sorted_average

    with chrono.Timer() as worst_bubble:
        for i in range(runs):
            assert bubble_sort(worst) == sorted_worst

    with chrono.Timer() as best_bubble:
        for i in range(runs):
            assert bubble_sort(best) == sorted_best

    with chrono.Timer() as huge_bubble:
        for i in range(runs):
            assert bubble_sort(huge) == sorted_huge

    print("Bubble sort [average]: {0} seconds".format(average_bubble.elapsed))
    print("Bubble sort [worst]: {0} seconds".format(worst_bubble.elapsed))
    print("Bubble sort [best]: {0} seconds".format(best_bubble.elapsed))
    print("Bubble sort [huge]: {0} seconds".format(huge_bubble.elapsed))

    print()

    with chrono.Timer() as average_quick:
        for i in range(runs):
            assert quick_sort(average) == sorted_average

    with chrono.Timer() as worst_quick:
        for i in range(runs):
            assert quick_sort(worst) == sorted_worst

    with chrono.Timer() as best_quick:
        for i in range(runs):
            assert quick_sort(best) == sorted_best

    with chrono.Timer() as huge_quick:
        for i in range(runs):
            assert quick_sort(huge) == sorted_huge

    print("Quick sort [average]: {0} seconds".format(average_quick.elapsed))
    print("Quick sort [worst]: {0} seconds".format(worst_quick.elapsed))
    print("Quick sort [best]: {0} seconds".format(best_quick.elapsed))
    print("Quick sort [huge]: {0} seconds".format(huge_quick.elapsed))

    print()

    with chrono.Timer() as average_insert:
        for i in range(runs):
            assert insertion_sort(average) == sorted_average

    with chrono.Timer() as worst_insert:
        for i in range(runs):
            assert insertion_sort(worst) == sorted_worst

    with chrono.Timer() as best_insert:
        for i in range(runs):
            assert insertion_sort(best) == sorted_best

    with chrono.Timer() as huge_insert:
        for i in range(runs):
            assert insertion_sort(huge) == sorted_huge

    print("Insertion sort [average]: {0} seconds".format(average_insert.elapsed))
    print("Insertion sort [worst]: {0} seconds".format(worst_insert.elapsed))
    print("Insertion sort [best]: {0} seconds".format(best_insert.elapsed))
    print("Insertion sort [huge]: {0} seconds".format(huge_insert.elapsed))

    print()

    with chrono.Timer() as average_python:
        for i in range(runs):
            assert sorted(average) == sorted_average

    with chrono.Timer() as worst_python:
        for i in range(runs):
            assert sorted(worst) == sorted_worst

    with chrono.Timer() as best_python:
        for i in range(runs):
            assert sorted(best) == sorted_best

    with chrono.Timer() as huge_python:
        for i in range(runs):
            assert sorted(huge) == sorted_huge

    print("Python sort [average]: {0} seconds".format(average_python.elapsed))
    print("Python sort [worst]: {0} seconds".format(worst_python.elapsed))
    print("Python sort [best]: {0} seconds".format(best_python.elapsed))
    print("Python sort [huge]: {0} seconds".format(huge_python.elapsed))