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])
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.