Sort algorithm/Talk

Here's a Python module for testing comparison-based sort routines written in Python. (Obviously this won't work for radix and trie sorts, but it should work for most others.) The purpose of this module is to verify that code presented as an implementation of a sort algorithm does, in fact, sort correctly. (Whether it is an implementation of the right algorithm is a little more difficult to verify mechanically.)

Reasons for giving algorithm implementations in Python rather than pseudocode are described on Algorithm/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()