Test many sorting algorithms using Python and Nose

Question

I'm trying to learn how to build a good test suite, using simple sorting as an example. Particularly, I am using Nose to generate all the tests based on a simple list of lists, where each sublist is a unit-test for each sorting method, as seen below:

from nose.tools import assert_equal
def check_sort(s, arr):
 assert_equal( s(arr), sorted(arr) )
def selection_sort(arr):
 """Repeatedly find the smallest element in the unsorted part
 and swap it with the first element in the unsorted part"""
 for i in xrange(len(arr)):
 min_val = min(arr[i:])
 min_ind = i + arr[i:].index(min_val)
 arr[i], arr[min_ind] = arr[min_ind], arr[i]
 return arr
def test_sorts():
 sorts = [selection_sort]
 for s in sorts:
 examples = [ [],\
 [1],\
 [1,1],\
 [1, 2, 3],\
 [1, 3, 2],\
 [2, 1, 3],\
 [2, 3, 1],\
 [3, 1, 2],\
 [3, 2, 1],\
 [-10, 35, 4, 99, 1003, 2],\
 [-10, 2, 35, 4, 4, 99, 99, 1003, 2]]
 for arr in examples:
 yield check_sort, s, arr

It seems to me that there has to be a better way of doing this, by using classes and more advanced methods to set-up and tear-down on the go. The caveat is that I would like to be able to extend the sorts list, adding more functions that implement bubble sort, merge sort, quick sort, etc. without having to create more tests by hand.

Any advice is appreciated.

Answer 1

You don't need backslashes for line continuation inside any pair of brackets. Remove them. Further, this formatting IMHO is quite strange anyway.

The second problem is that you are both modifying the sorted array and returning it. Note how list.sort modifies but doesn't return and sorted returns but doesn't modify. Considering how slow your sort is, a copy at the start wouldn't hurt.

Your docstring is also all wrong; docstrings should mention user-facing concerns, not implementation detail. A thorough one might say

Sort the input container in place and return it.
This sorts in n2 time and is not guaranteed to be stable.
The input must be mutable and its elements must have total order.

Talking about the tests, I'm going to ignore the framework and focus on the meat of the problem. I would try and get automatic test generation down first.

You really want two things. First, for small values do an exhaustive check:

from itertools import product
def test_sort_small(sort):
 for length in range(8):
 for sortable in product(range(4), repeat=length):
 sortable_copy = list(sortable)
 sorted_copy = sort(sortable_copy)
 assert sorted_copy is sortable_copy
 assert sorted_copy == sorted(sortable)

For large values do a random check.

import random
def test_sort_large(sort):
 for log_length in range(4, 12):
 for length in range(2**log_length-4, 2**log_length+5):
 sortable = [random.randint(0, 3) for _ in range(length)]
 sortable_copy = list(sortable)
 sorted_copy = sort(sortable_copy)
 assert sorted_copy is sortable_copy
 assert sorted_copy == sorted(sortable)

Tie those together

def test_sorts(sorts={selection_sort}):
 for sort in sorts:
 test_sort_small(sort)
 test_sort_large(sort)
test_sorts()

Put this logic in whatever framework you want.

Personally I'd also throw in a test with a more compex object, but it shouldn't really matter.

I would definitely try testing with another container, such as a bytearray, if you want to support them.

You could easily get a stable sort, so you might want to add that and add associated tests.