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. To solve it, we can do heap sort, insertion sort, merge sort, quick sort, selection sort and so on. In the end, we will have a set of five tests for each test case. If in the future, I’ll come up with a new test case, I’ll have to write five tests to check 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.