Test Driven Revision

For my interview this week, I was sent a list of things to prep. One of them was sorting algorithms.

The best way for me to remember and understand them is to code them, and I decided to go through the list on Wikipedia and code them in Java – even the recursive ones. I think recursively much better in Haskell but interviewers aren’t always cool when you ask to solve the problem in a non-standard language (I lucked out last time).

Because I was writing a lot of similar code, I created an interface first, so that I could write parametrized test cases. These methods should really be static, but I compromised on that in order to make my testing easier.

 public interface Sort {
     public abstract void sort(int[] array);
 }

This was pretty easy, and allowed me to write a parametrized test case that would run all my tests on anything implementing Sort. So I had some code that looked like this:

 private Sort sort;

 public TestSort(Sort sort) {
     this.sort = sort;
 }

 @Parameters
 public static Collection regExValues() {
     return Arrays.asList(new Object[][] {
         { new BubbleSort() },
         { new InsertionSort() },
         { new ShellSort() },
         { new MergeSort() },
         { new QuickSort() },
         { new CountingSort() } });
 }

And as I created each new class I just added it to my list of parameters, and all my tests (labeled @Test) would be run on them as well. My tests were pretty repetitive and probably could have been parametrized as well, but because I was testing all these different classes I opted for slightly more code in the tests. (Full test code below)

This approach really reduced my coding time, because once I’d set up the interface and the tests I could get a new class working very easily without using cut and paste. I also determined what I wanted to test: null, empty, one element, two elements sorted, two elements unsorted, odd number of elements, even number of elements, and longer with duplicates. When I added an extra test case part way through, it applied to all my previous classes. Determining the tests in advance was more effective than ad-hoc testing, for example, the odd number of elements test was helpful in catching an off-by-one bug.

It also encouraged me to write better code. I might write the function, understand it, and just have a little bug – but I’d keep at it, because I wanted all the tests to pass before I moved on. I also had one bug that was resulting in an array with just two elements reversed – I didn’t notice that staring at the debug statement, it looked fine. But of course, my tests noticed! And the time when I wrote the algorithm right first time? That was pretty nice! Even if it was the super easy CountingSort.

Sorted
Credit: flickr / David Singleton

Full test code is below if you have any use for it! Note – parameterized test cases are JUnit 4, and I’ve just used ints rather than a Generic <extends Comparable> approach – if you decide to do that, just change to Integer or anything else that implements Comparable.

import java.util.Arrays;
import java.util.Collection;

import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class TestSort {

	private Sort sort;

	public TestSort(Sort sort) {
		this.sort = sort;
	}

	@Parameters
	public static Collection regExValues() {
		return Arrays.asList(new Object[][] {
				{new BubbleSort()},
				{new InsertionSort()},
				{new ShellSort()},
				{new MergeSort()},
				{new QuickSort()},
				{new CountingSort()}});
	}

	// null array
	@Test(expected=IllegalArgumentException.class)
	public void testNullArray() {
		sort.sort(null);
	}

	// empty array
	@Test
	public void testEmptyArray() {
		int[] array = new int[0];
		sort.sort(array);
		Assert.assertArrayEquals(new int[0], array);
	}

	// one element array
	@Test
	public void testOneElementArray() {
		int[] array = {42};
		int[] test = {42};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}

	// two element array ordered
	@Test
	public void testTwoElementOrdArray() {
		int[] array = {7, 42};
		int[] test = {7, 42};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}

	// two element array unordered
	@Test
	public void testTwoElementUnordArray() {
		int[] array = {42, 7};
		int[] test = {7, 42};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}

	// odd numbered element array
	@Test
	public void testOddNoElementsArray() {
		int[] array = {42, 68, 9, 7, 100, 36, 27};
		int[] test = {7, 9, 27, 36, 42, 68, 100};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}

	// even numbered element array
	@Test
	public void testEvenNoElementsArray() {
		int[] array = {42, 68, 9, 7, 100, 36, 27, 99};
		int[] test = {7, 9, 27, 36, 42, 68, 99, 100};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}

	// array in reverse order
	@Test
	public void testReverseOrder() {
		int[] array = {100, 99, 68, 42, 36, 27, 9, 7};
		int[] test = {7, 9, 27, 36, 42, 68, 99, 100};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}

	// longer array
	@Test
	public void testLongerArray() {
		int[] array = {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10};
		int[] test = {10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94};
		sort.sort(array);
		Assert.assertArrayEquals(test, array);
	}
}

One thought on “Test Driven Revision

Leave a Reply