What does it take to test a sorting routine?

Thanks to all of you who have taken part in yesterday’s selection-sort challenge, and everyone who’s still submitting code.  (If you haven’t yet done so but plan to, then please don’t read this article until you’ve written your code according to the rules laid down in that article, otherwise you’ll see hints that you probably don’t want to see up front.)

I promised yesterday that I’d post some ideas about a test-suite in a subsequent article: this is it.

First up, here is the Ruby code that I wrote, and which I want to test. (I deliberately wrote it using low-level constructs, avoiding list operations, so it should look familiar to people who are used to other languages.)

def selection_sort!(a)
  for i in 0..a.size-2 do
    # Invariant: a[0..i-1] contain smallest values in order
    smallest = i
    for j in i+1..a.size-1 do
      # Invariant: a[smallest] is the smallest value in a[i..j-1]
      if a[j] < a[smallest]
        smallest = j
      end
    end
    a[i], a[smallest] = a[smallest], a[i]
  end
end

Fairly simple code.  (The function name ends with an exclamation mark because it updates the array a destructively.  This is a helpful naming convention in Ruby, stolen from Scheme.)

So what do we need to test?

Sorting the empty array

First, the degenerate case.  This is always a good way to start testing — in the words of Kernighan and Pike, “Make sure your code ‘does nothing’ gracefully” — a rule that they follow with a more general version, “Test programs at their boundary values”.  So first up, we need to test that sorting an empty array does the right thing, i.e. nothing at all.

In a comment on the previous article, Sean Conner wrote:

[My] code doesn’t handle 0 sized arrays (as my tests bore out) but it works on arrays of 1 or more elements. Personally, I don’t consider a 0-element array as being valid, but that’s me.

I hope Sean won’t mind me picking on him, but I find this absolutely bewildering.  Of course an empty set is a perfectly good set. It’s just as valid a set as an empty string is a valid string: how would we feel about a strlen() function that didn’t work on empty strings?

Or think about the ls (Unix) and dir (Windows) commands that list files in the working directory, sorted: what would we think of such a program if it didn’t work in empty directories, due to the sort routine not working on empty arrays?

So, rule number one: if your program fails on an empty array, it fails.  Test on [].

Oh, and rule number two is like unto it: a routine needs to be able to sort an array of a single element (i.e., again, do nothing).  I use the array [0].

Repeated elements

It’s not unusual for programs to branch the wrong way on equality — something else that Kernighan and Pike’s rules remind us about — so it’s often worth testing code against lists that have repeated elements.

For sorting, this is perhaps less likely to uncover bugs than when searching, but it’s still a case well worth covering.  So as well as an empty array and a single-element array, my test suite includes arrays of two and three identical elements: [0, 0] and [0, 0, 0].

Elements in and out of order

Some broken sorts will appear to do the right thing if the elements are already in order — for example, the O(1) sort consisting of no statements at all will do this.  Others, more rarely, might stumble on the right answer if the input is sorted in reverse.  Yet others will be caught out by cases in which some of the elements are already in order and others are not.  So my set of test cases includes in-order and out-of-order two-element  arrays [0, 1] and [1, 0], plus the full set of six permutations of [0, 1, 2].

Because repeated elements can also cause problems, I also threw in [0, 1, 1] and the other two permutations of that array.

Since all the test-cases so far have been of very small arrays — three or fewer elements — I added the sequences 1..10 and 10..1, ascending and descending.

MAXINT

I admit it didn’t occur to me to test whether an array containing MAXINT is properly sorted, but some commenters on the original post have found bugs in their routines when the largest representable integer is part of the array.

I don’t have a test for this because I’m using Ruby, which has no MAXINT: it automatically promotes numbers from Fixed to Bignum when they get too big to fit into the Fixed representation.  (It feels odd that we still have high-level languages that don’t do this: coping with integer overflow is a reasonable thing to do in C programs, but it seems bizarre in Java.)

Everything in together

I think that the cases I’ve listed above cover all the edges, so I capped off my set of canned tests with a slightly bigger and more random example, including some negative numbers and a repeated value.  I used [42, 9, 17, 54, 602, -3, 54, 999, -11], but it could have been anything.  I also added the already-sorted version of that same array, because — hey, why not?  Tests are cheap!

Random testing

Is that enough?  Well, it might be.  But it’s surprising how often purely random test-cases can shake out bugs that carefully designed test-cases miss.  Barton P. Miller and co-authors, in an article in the December 1990 Communication of the ACM, described how they tested almost 90 Unix utilities, on seven different versions of the operating system, and found that a quarter of them could be crashed simply by feeding them a random stream of input characters.  In one case (running refer on a Sequent Symmetry under Dynix 3.0) they were able to crash the operating system!

Ever since I read that paper — and I am a bit shocked to find that it was twenty years ago! — I’ve had a healthy respect for value of random testing.  Accordingly, I extended my test-suite with a set of randomly generated arrays to sort.  (I used ten arrays each of 100 elements, chosen in the range -500,000 to 499,999, but it’s trivial to make more, or change or randomise their size, or tweak the range of values.)

How do we test for correctness?

So there I am with 19 hand-crafted test-case arrays to sort, and ten (or more) randomly generated ones.  What does my actual test-harness look like?

The obvious thing to do is check that after sorting, each array is indeed sorted — something like

for i in (0..array.size-2) { assert array[i] <= array[i+1] }

But that’s not rigorous enough.  For example, it would report success for the O(n) non-sort that sets all elements of the array to zero.  So we also need to check that the result of the sort routine leaves the array elements as a permutation of what they were before.

We might check that the new array is a permutation of the old by ensuring that they are the same size and that each element in the source array is also in the sorted array.  But that can fail when the source array has repeated elements.  For example, consider a broken sort that takes the input [0, 0, 1] and yields the result [0, 1, 1].  The output array is the same size as the input array, and each element in the input is also in the output, but the sort is still broken.  Not only that, but the simple way of doing this check is O(n^2), which is just as expensive as the sort itself.

So as it turns out, the simplest approach is just to test against a known-good sort routine.  Since pretty much every environment has one of these, it’s easy to do; and since the system sort routines will in nearly every case use an O(n log n) algorithm, doing this additional sort and an O(n) comparison will also be much quicker than the naive permutation test — at least, for big arrays.

So that’s what I did: I sorted each test-case array once with my selection-sort routine and once with Ruby’s built-in sort function, and compared the two sorted arrays for equality.

My testing script

In case anyone cares, then, here is the complete testing script that I used:

tests = [
         [],
         [ 0 ],
         [ 0, 0 ],
         [ 0, 0, 0 ],
         [ 0, 1 ],
         [ 1, 0 ],
         [ 0, 1, 2 ],
         [ 0, 2, 1 ],
         [ 1, 0, 2 ],
         [ 1, 2, 0 ],
         [ 2, 0, 1 ],
         [ 2, 1, 0 ],
         [ 0, 1, 1 ],
         [ 1, 0, 1 ],
         [ 1, 1, 0 ],
         [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ],
         [ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ],
         [ 42, 9, 17, 54, 602, -3, 54, 999, -11 ],
         [ -11, -3, 9, 17, 42, 54, 54, 602, 999 ],
]

random_tests = []
10.times do
  a = []
  rand(100).times do
    a << rand(1000000)-500000
  end
  random_tests << a
end

ntests = 0
nok = 0
(tests + random_tests).each_with_index do |a, i|
  copy = a.clone
  selection_sort!(copy)
  if (copy == a.sort)
    nok += 1
  else
    puts "failed test #{i}: [#{a.join(' ')}] -> [#{copy.join(' ')}]"
  end
  ntests += 1
end
printf "passed %d of %d tests (%d%%)\n", nok, ntests, 100*nok/ntests

I suggest that this is a pretty good set of tests (especially if you turn up the number, size and range of the randomly generated arrays), and I’d like to humbly suggest that those of you who have claimed success for your routines might like to translate this test suite into your implementation language and check that your routines really do work.  (If you do this, please post the results as a comment on this article.)

But I’m certainly not claiming that this test-suite is complete and exhaustive!  If you see any important cases that I missed, please point them out in the comments.  Hopefully the outcome of this will be a nice, solid and rigorous test-harness for sort routines, which we can use again when we come to do more interesting sorting exercises later.

What I got wrong

Finally, honesty compels me to admit to the two mistakes I made in my own selection-sort routine.  Well, three.

First, Error Zero: I was too impatient to run the code.  Yes, after all the good work I’d done preaching about invariants, bound functions and preconditions and postconditions, I stupidly ignored my own awesome advice and didn’t think through my code properly, using these tools, before running it.

So, then: because of that, Error One was that I started the inner loop at one more than the value of the outer loop (which in itself is fine), but started the which-index-has-the-lowest-value-we’ve-seen-so-far variable as nil rather than the value of the outer loop-counter.

Error Two was a really dumb one, a mere typo.  I had the swap statement inside the inner loop rather than immediately after it.

These are stupid mistakes, and I kind of wish I’d not told you about them now.  Oh well.

I’ll get it right next time, for sure!

—

References

Miller, Barton P., Lars Frederiksen and Bryan So.  1990.  An Empirical Study of the Reliability of UNIX Utilities. Communications of the ACM, 33(12).