Reasons for giving algorithm implementations in Python rather than pseudocode are described on Algorithms/Talk?.
I call this module sorttest.py.
"""This is a Python module for testing sort routines. The sort routines must obey the following interface: def sort(array, cmp=lambda x, y: x > y): It doesn't matter what it returns, but it must not throw an exception in any of the tests. Note that in Python, the parameter names are part of the interface, so the parameters must be called 'array' and 'cmp'. (There can be additional optional parameters, though.) When it returns, it should have mutated the array 'array' so that it contains the same items (in the sense of 'is'), but possibly in a different order. The new order must be such that, for any i in range(len(array-1)), cmp(array[i], array[i+1]) is false. So, by default, it sorts ascending. It must not mutate anything the array points to --- that's cheating --- but this is hard to test. """ import random def bubblesort(array, cmp=lambda x, y: x > y): """The simplest working sort routine, for testing purposes. This is here to make it possible to test sort-testing routines.""" indices = range(len(array)) indices.reverse() for j in indices: for i in range(j): if cmp(array[i], array[i+1]): (array[i], array[i+1]) = (array[i+1], array[i]) OutOfOrder = "sorttest.OutOfOrder" ScrewedUpArray = "sorttest.ScrewedUpArray" def brokensort1(array, cmp=lambda x, y: x > y): """Broken 'sort' routine that overwrites the whole array with 1 element.""" for i in range(len(array)): array[i] = array[0] def brokensort2(array, cmp=lambda x, y: x > y): """Broken 'sort' routine that bubblesorts backwards.""" bubblesort(array, lambda x, y, cmp=cmp: cmp(y, x)) def testsort_onearray(array, sort, cmp=None): """Given a sort routine and an array, raise an exception if it sorts wrong. """ arraycopy = array[:] # copy array if cmp is None: sort(array) else: sort(array, cmp) # verify that the array is in order if cmp is None: cmp = lambda x, y: x > y for i in range(len(array)-1): if cmp(array[i], array[i+1]): raise OutOfOrder, (i, arraycopy, array, array[i], array[i+1]) # verify that it consists of the elements of the original array: # doesn't contain any fewer elements: if len(array) != len(arraycopy): raise ScrewedUpArray, ("array length changed", arraycopy, len(array), len(arraycopy)) # and doesn't contain any more copies of any element than the original # array: idmap = {} for i in arraycopy: if not idmap.has_key(id(i)): idmap[id(i)] = 0 idmap[id(i)] = idmap[id(i)] + 1 for i in array: if not idmap.has_key(id(i)): raise ScrewedUpArray, ("element wasn't in original array", arraycopy, i) idmap[id(i)] = idmap[id(i)] - 1 if idmap[id(i)] < 0: raise ScrewedUpArray, ("element was in original array fewer times", arraycopy, i) def qwi(string): """Turn a string containing a list of ints into a list of ints.""" return map(int, string.split()) def testsort(sort): """Test a sort routine on a variety of inputs. Main entry point.""" def backwards(x, y): return x < y # simplest case: empty array testsort_onearray([], sort) testsort_onearray([], sort, backwards) # sorting a short already-in-order array testsort_onearray([1, 2, 3], sort) testsort_onearray([3, 2, 1], sort, backwards) # an actual array that needs some sorting testsort_onearray([4, 2, 5, 3, 6, 0], sort) testsort_onearray([4, 2, 5, 3, 6, 0], sort, backwards) # and with duplicate elements testsort_onearray(qwi('0 0 1 2 2 3 3 3 4 5 5'), sort) testsort_onearray(qwi('5 5 5 4 3 2 1 1'), sort, backwards) testsort_onearray(qwi('0 0 1 2 2 3 3 3 4 5 5'), sort, backwards) testsort_onearray(qwi('5 5 5 4 3 2 1 1'), sort) # more more-or-less random tests with lists of integers testsort_onearray(qwi('1 33 1 3 1 3 42 1 5 5 1 -1 17 40'), sort) testsort_onearray(qwi('1 1 1 1 1'), sort) testsort_onearray([1], sort) # I'd like to use a bigger random list, but O(N^2) sorts get too slow rg = random.Random() testsort_onearray([rg.randint(0, 1000) for x in range(100)], sort) # verify that it works on things other than integers testsort_onearray('vow to bring enlightenment to all sentient beings' .split(), sort) testsort_onearray(map(lambda x: [x], qwi('1 3 1 4 5')), sort, lambda x, y: x[0] > y[0]) def test(): """Test routine to verify that sort-testing routines work. This routine runs when the module loads to ensure that it still works correctly. """ testsort_onearray([], bubblesort) testsort_onearray([], bubblesort, lambda x, y: x < y) testsort_onearray([1, 2, 3], bubblesort) testsort_onearray([1, 2, 3], bubblesort, lambda x, y: x < y) testsort_onearray([3, 2, 1], bubblesort) testsort_onearray([3, 2, 1], bubblesort, lambda x, y: x < y) testsort_onearray(map(int, '2 3 3 1 41 31 1 0 1'.split()), bubblesort) ok = 0 try: testsort_onearray([1, 2], brokensort2) except: ok = 1 assert ok ok = 0 try: testsort_onearray([1, 2], brokensort1) except: ok = 1 assert ok testsort(bubblesort) ok = 0 try: testsort(brokensort1) except: ok = 1 assert ok ok = 0 try: testsort(brokensort2) except: ok = 1 assert ok test()