Python - insertion sort

Question

_{Series post - I am reading through Introduction to Algorithms, 3rd Edition implementing each algorithm as I read them.}

---

Pretty basic insertion sort. Only considering numbers initially - how could I make this better and/or have better tests?

def insertion_sort(numbs):
    for cur_index in range(1, len(numbs)):
        cur_val = numbs[cur_index]

        lookup_index = cur_index - 1

        while lookup_index >= 0 and numbs[lookup_index] >= cur_val:
            numbs[lookup_index + 1] = numbs[lookup_index]
            lookup_index -= 1
        numbs[lookup_index + 1] = cur_val

    return numbs


def check_insertion_sort(input, expected):
    result = insertion_sort(input)
    if result != expected:
        print "Result={} does not equal expected={} for input={}".format(result, expected, input)
    else:
        print "Success for input={}".format(input)


check_insertion_sort([5, 2, 4, 6, 1, 3], [1, 2, 3, 4, 5, 6])
check_insertion_sort([190, 2, 4, 6, 1, 3], [1, 2, 3, 4, 6, 190])
check_insertion_sort([-190, 2, 4, 6, 1, 3], [-190, 1, 2, 3, 4, 6])
check_insertion_sort([0, 0, 4, 6, 1, 3], [0, 0, 1, 3, 4, 6])
check_insertion_sort([0, 0], [0, 0])
check_insertion_sort([1, 0], [0, 1])

Answer 1

First of all, awesome that you have written tests!

However, your checker is a bit verbose on the matching case. It is often considered good practice for automated tests to be as noise-free as possible. Consider the following outputs:

Success for input=...testcase...
... 300 lines of success ...
Success for input=...testcase...
Result=... does not equal expected=... for input=...
Success for input=...testcase...
... 300 lines of success ...
Success for input=...testcase...

Ok, you have written just a few testcases, but I think you see my point: you'll miss the errors. Better would be just

Result=... does not equal expected=... for input=...

Failures: 1, Success: 601

Better: use a testing framework like unittest, py.test or doctest. Here's how it looks like doctest:

def insertion_sort(numbs):
    """
    >>> insertion_sort([5, 2, 4, 6, 1, 3])
    [1, 2, 3, 4, 5, 6]
    >>> insertion_sort([190, 2, 4, 6, 1, 3])
    [1, 2, 3, 4, 6, 190]
    >>> insertion_sort([-190, 2, 4, 6, 1, 3])
    [-190, 1, 2, 3, 4, 6]
    >>> insertion_sort([0, 0, 4, 6, 1, 3])
    [0, 0, 1, 3, 4, 6]
    >>> insertion_sort([0, 0])
    [0, 0]
    >>> insertion_sort([1, 0])
    [0, 1]
    """
    for cur_index in range(1, len(numbs)):
        cur_val = numbs[cur_index]

        lookup_index = cur_index - 1

        while lookup_index >= 0 and numbs[lookup_index] >= cur_val:
            numbs[lookup_index + 1] = numbs[lookup_index]
            lookup_index -= 1
        numbs[lookup_index + 1] = cur_val

    return numbs


if __name__ == "__main__":
    import doctest
    doctest.testmod()

Now, this is a bit verbose, so my preference would probably to use py.test or nosetests, but the advantage of doctest is that it's built-in, and for simple tests it is sufficient.

Now, for another point. Your sorting is both in-place, and returns the list again.

For instance:

>>> example = [6, 7, 1, 2]
>>> result = insertion_sort(example)
>>> result
[1, 2, 6, 7]
>>> example
[1, 2, 6, 7]

Suggestion: if you do in-place sort, make sure it is documented that the function modifies the input array. In general, I would prefer not returning the result, as to limit confusion.

I can't really see anything wrong with the implementation itself, but I'm not familiar enough with insertion sort.

Using range is fine for short lengths, but as this is a list-sort, you don't really know the values len(numbs) will take. Maybe use xrange instead? (Or better: upgrade to Python 3!).

One thing I would really really like to advice is switching to Python 3 for learning. Python 2 is only supported up-to 2020, and a lot of people would be happy if more people learn Python 3 instead.