Comparing execution time of in-place and immutable implementation of insertion sort in Python 3

insertion.png

insertion_sort.py

import random
import timeit
import json


def insertion_sort(items):
    """Insertion Sort: In place list modification"""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0:
            if items[j] > key:
                items[j+1] = items[j]
                j -= 1
            else:
                break
        items[j+1] = key
    return items


def insertion_sort2(items):
    """Insertion Sort: Returning copies of list and using recursion"""
    
    def insert(key, sorted_items):
        for i, x in enumerate(sorted_items):
            if key < x:
                return sorted_items[:i] + [key] + sorted_items[i:]
        return sorted_items + [key]

    def iterate(i, result):
        if i == (len(items)-1):
            return insert(items[i], result)
        else:
            return iterate(i+1, insert(items[i], result))

    return iterate(1, items[:1])


def shuffled(items):
    items = list(items)
    random.shuffle(items)
    return items


def compare_timit(f):
    nums = [10] + list(range(50, 1000, 50)) + [990] # > 990 results in max recursion depth exceeded...
    timings = {}
    for i in nums:
        stmt = '{func}(shuffled(range({size})))'.format(func=f.__name__, size=i)
        setup = 'from __main__ import shuffled, {func}'.format(func=f.__name__)
        print(stmt)
        time = timeit.timeit(stmt, setup=setup, number=1000)
        timings[i] = time
    return timings
        

if __name__ == '__main__':
    inplace = compare_timit(insertion_sort)
    immutable = compare_timit(insertion_sort2)
    with open('timings.json', 'w') as f:
        json.dump({'inplace': inplace, 'immutable': immutable}, f, indent=4)
    

plotgraph.py

#!/usr/bin/python2.7

import json
from collections import OrderedDict

import matplotlib.pyplot as plt


def plot():
    with open('timings.json') as f:
        timings = json.load(f)
        inplace = OrderedDict(sorted((int(k), float(v)) for k, v in timings['inplace'].iteritems()))
        immutable = OrderedDict(sorted((int(k), float(v)) for k, v in timings['immutable'].iteritems()))
        plt.title('Insertion Sort')
        plt.plot(inplace.keys(), inplace.values(), 'b-', immutable.keys(), immutable.values(), 'r-')
        plt.legend(('By inplace list modification', 'By returning copies of list'), 'upper left')
        plt.axis([0, 990, 0, 80])
        plt.ylabel('Python timeit with n=1000 (sec)')
        plt.xlabel('Length of list')
        plt.savefig('insertion.png')


if __name__ == '__main__':
    plot()