2
\$\begingroup\$

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])
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.