Unit testing algorithms

In the last weeks, I’ve been improving my computer science knowledge by solving programming problems. Since these problems have multiple solutions, I find myself writing duplicated unit tests. And refactoring these tests is cumbersome (if find&replace doesn’t work).

To make the point clear, I’m going to pick a problem with many possible implementations: sorting an integer array. Let’s keep things simple and solve the problem using heap sort, insertion sort, merge sort, quick sort, and selection sort. When the time comes to write the tests, all of the tests will be duplicated between implementations. If, in the future, I come up with a new test case, I have to write (copy&paste) that test to the test class of each implementation. This is far from optimal.

After doing a bit of digging, I found a convenient solution to removing the duplication: JUnit5’s @ParameterizedTest and @ValueSource. I had to do a bit of refactoring: I created a new interface that declares the sort method, and I made sure that all *sort classes implement the interface properly (you did create one class per implementation, right?). After that, it was just a matter of wiring up the tests.

Cool! 🙂 Before, the unit tests were all over the place, and not all implementations had all the corner cases tested. Soon enough, I found that the QuickSort implementation throws StackOverflowError when the input array contains duplicate values. You can find the source code here.