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.

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);
	}
}