Testing the Dutch national flag task

Question

I recently coded the Dutch national flag problem in Java and wrote some tests. The array in zero-indexed. Please take a look at how I verify that elements of the output array are in the right order. It's the method verifyDutch

The Dutch national flag problem

public static void dutchFlag(int[] input, int mid) {
    if (input == null || input.length < 2) {
        return;
    }
    int i = 0; // the end of the red region
    int j = 0; // the element under consideration
    int k = input.length - 1; // the start of the blue region
    while (j <= k) {
        if (input[j] < mid) {
            swap(input, i, j);
            i++;
            j++;
        } else if (input[j] == mid) {
            j++;
        } else {
            swap(input, j, k);
            k--;
        }
    }
}

Testing

public class FlagSortsTests {

    @Test
    public void testDutchWithRandom() {
        int[] input = new int[10];
        Random random = new Random();
        for (int i = 0; i < input.length; i++) {
            input[i] = random.nextInt(100);
        }
        int mid = input[random.nextInt(input.length - 1)];
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    @Test
    public void testDutchSmallestMid() {
        int[] input = { 12, 34, 781, -1 };
        int mid = -1;
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    @Test
    public void testDutchLargestMid() {
        int[] input = { 12, 34, 781, -1 };
        int mid = 781;
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    @Test
    public void testDutchWithoutMid() {
        int[] input = { 12, 34, 781, -1 };
        int mid = 90;
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    private void verifyDutch(int[] input, int mid) {
        if (input == null || input.length < 2) {
            return;
        }
        for (int i = 1; i < input.length; i++) {
            if (input[i] < mid) {
                Assert.assertTrue(input[i - 1] < mid);
            } else if (input[i - 1] == mid) {
                Assert.assertTrue(input[i] >= mid);
            } else if (input[i - 1] > mid) {
                Assert.assertTrue(input[i] > mid);
            }
        }
    }

Update #1

The assert failure messages are wrong. Let me delete them until I write something more infomative

Answer 1

Black hole

If the input is invalid, then there's no feedback to the caller, you just swallow the problem. This may be ok for your situation, but generally I'd try to make sure the caller has some way of knowing if the operation did anything.

if (input == null || input.length < 2) {
    return;
}

You also don't have any tests for these edge cases (which may be fine if you really don't care about them, but then why bother checking the input at all).

Naming

Rather than giving your variables a single character and a descriptive comment at the top, consider giving the variable a meaningful name endOfRed. You don't need the comment and you're not going to forget what the variable refers to as you move through the code.

int i = 0; // the end of the red region

Random

From a human perspective, running a bunch of tests with random values can be very reassuring. However you want your unit tests to be repeatable and reliable. Having random numbers generated to seed your tests can result in intermittent failures which you want to avoid (consider the impact if this was part of a larger build process). If you do want to use random, then it would be a good idea to make sure that on failure the input data set is logged / displayed. The only thing worse than an intermittent failure is one that you can't reproduce.

assertTrue

I'm not a huge fan of assertTrue. People will often use it to assert equality and the feedback you get from assertTrue (expected true, was false) is a lot worse than the feedback you get if you're asserting equality (expecting x,y,z but got x,y). When stuff goes wrong you want to know what values were being asserted against and often assertTrue hides that. From your comments, it looks like you may have had messages which might have been better...

The hole in your tests

You don't actually check that the flags you're producing are the flags for the input. So, I could replace your code with the following:

public static void dutchFlag(int[] input, int mid) {
    for(int i = 0; i < input.length;i++) {
        input[i] = mid;
    }
}

Even though this code is clearly wrong (since it's essentially a whitewash), all of your tests would pass. I think your tests would actually be more expressive (and more reliable) if instead, you had three utility functions... findRed, findWhite and findBlue. These would take in the generated flag and return an array of the numbers to the left of mid, equal to mid, to the right of mid. So, findRed might look something like this:

private int[] findRed(int[]flag, int mid) {
    for(int index = 0; index < flag.length; index++) {
        if(flag[index] >= mid) {
            return Arrays.copyOfRange(flag, 0, index);
        }
    }
    return flag;
}

A test using it, might then look like:

@Test
public void testDutchWithoutMids() {
    int[] input = {12, 34, 781, -1};
    int mid = 90;

    FlagSorts.dutchFlag(input, mid);

    assertThat(findRed(input, mid)).containsExactlyInAnyOrder(12, 34, -1);
    assertThat(findWhite(input, mid)).isEmpty();
    assertThat(findBlue(input, mid)).containsExactlyInAnyOrder(781);
}

This validates that the flag sections actually contain the numbers that you're expecting them to and if there's any errors you get told what the expected values were and what the actual values are. Note, I'm using AssertJ for my assertions.