Java 8 Lambdas applied to QuickSort algorithm

In this article I'm going to review Java 8 Lambdas use cases after I've watched the Lambdas have come to Java! screencast from Typesafe. As a nice example, I've decided to count comparisons in the Quicksort algorithm.

1. Basic algorithm.
2. Inline lambdas.
3. Method references.

Basic algorithm

Here is a basic implementation where we count comparisons in the Quicksort algorithm:

public class QuickSort {
    public static long countComparisons(List<Integer> a) {
        if (a.size() <= 1) return 0;
        int p = getPivot(a);
        int i = 1;
        for (int j = 1; j < a.size(); j++) {
             if (a.get(j) < p) {
                 if (j > i) swapInList(a, i, j);
                 i++;
             }
        }
        swapInList(a, 0, i - 1);
        return countComparisons(a.subList(0, i - 1)) +
                countComparisons(a.subList(i, a.size())) + a.size() - 1;
    }

    private static Integer getPivot(List<Integer> a) {
        return a.get(0);
    }

    private static void swapInList(List<Integer> a, int i, int j) {
        int temp = a.get(j);
        a.set(j, a.get(i));
        a.set(i, temp);
    }
}

Above the getPivot method is a crucial point of the Quicksort algorithm. The choice of pivot affects the algorithm performance. So I'd like to be able to provide an external implementation of this method and use "median of three" rule, for example. This rule means choosing the median of the first, middle and last element as a pivot.

Inline lambdas

First let's use lambdas in the straightforward way. This is what QuickSort.countComparisons method will look like:

public static long countComparisons(List<Integer> a,
                                    Function<List<Integer>, Integer> getPivot) {
    if (a.size() <= 1) return 0;
    int p = getPivot.apply(a);
    int i = 1;
    for (int j = 1; j < a.size(); j++) {
         if (a.get(j) < p) {
             if (j > i) swapInList(a, i, j);
             i++;
         }
    }
    swapInList(a, 0, i - 1);
    return countComparisons(a.subList(0, i - 1), getPivot) +
            countComparisons(a.subList(i, a.size()), getPivot) + a.size() - 1;
}

And here are the unit tests:

public class TestQuickSort {
    private List<Integer> unsorted;

    @Before
    public void setUp() {
        unsorted = Arrays.asList(9, 5, 1, 10, 6, 3, 2, 9, 3, 2);
    }

    @Test
    public void testFirstAsPivot() {
        Assert.assertEquals(22, QuickSort.countComparisons(unsorted, a -> a.get(0)));
    }

    @Test
    public void testLastAsPivot() {
        Assert.assertEquals(23, QuickSort.countComparisons(unsorted, a -> {
            QuickSort.swapInList(a, 0, a.size() - 1);
            return a.get(0);
        }));
    }

    @Test
    public void testMedianOfThreeAsPivot() {
        Assert.assertEquals(21, QuickSort.countComparisons(unsorted, a -> {
            int l = a.get(0), m = a.get((a.size() - 1) / 2), r = a.get(a.size() - 1);
            if ((m >= l && m <= r) || (m >= r && m <= l)) {
                QuickSort.swapInList(a, 0, (a.size() - 1) / 2);
            } else if ((r >= l && r <= m) || (r >= m && r <= l)) {
                QuickSort.swapInList(a, 0, a.size() - 1);
            }
            return a.get(0);
        }));
    }
}

Now all this is cool except that it's hard to debug, maintain and reuse. So if there is an exception being thrown from inside the lambda, you'll see rather cryptic stacktrace using anonymous class syntax. For example, let's add division by zero to a lambda and see the stacktrace:

@Test
public void testFirstAsPivot() {
    Assert.assertEquals(22, QuickSort.countComparisons(unsorted, a -> a.get(0) / 0));
}

java.lang.ArithmeticException: / by zero
 at TestQuickSort.lambda$testFirstAsPivot$0(TestQuickSort.java:22)
 at TestQuickSort$$Lambda$2/1766822961.apply(Unknown Source)
 at QuickSort.countComparisons(QuickSort.java:71)
 at TestQuickSort.testFirstAsPivot(TestQuickSort.java:22)

Not a big issue some will say. But in the next section let's refactor the lambdas into methods and use method references.

Method references

First let's move the choice of pivot logic to a separate class:

public class PivotChoice {
    public static Integer getFirst(List<Integer> a) {
        return a.get(0);
    }

    public static Integer getLast(List<Integer> a) {
        QuickSort.swapInList(a, 0, a.size() - 1);
        return a.get(0);
    }

    public static Integer getMedianOfThree(List<Integer> a) {
        int l = a.get(0), m = a.get((a.size() - 1) / 2), r = a.get(a.size() - 1);
        if ((m >= l && m <= r) || (m >= r && m <= l)) {
            QuickSort.swapInList(a, 0, (a.size() - 1) / 2);
        } else if ((r >= l && r <= m) || (r >= m && r <= l)) {
            QuickSort.swapInList(a, 0, a.size() - 1);
        }
        return a.get(0);
    }
}

Second let's update the unit tests:

@Test
public void testFirstAsPivot() {
    Assert.assertEquals(22, QuickSort.countComparisons(unsorted, PivotChoice::getFirst));
}

@Test
public void testLastAsPivot() {
    Assert.assertEquals(23, QuickSort.countComparisons(unsorted, PivotChoice::getLast));
}

@Test
public void testMedianOfThreeAsPivot() {
    Assert.assertEquals(21, QuickSort.countComparisons(unsorted, PivotChoice::getMedianOfThree));
}

Now it already looks much prettier. But let's again add division by zero at the same place and see the stacktrace:

public static Integer getFirst(List<Integer> a) {
    return a.get(0) / 0;
}

java.lang.ArithmeticException: / by zero
 at PivotChoice.getFirst(PivotChoice.java:8)
 at TestQuickSort$$Lambda$2/1496724653.apply(Unknown Source)
 at QuickSort.countComparisons(QuickSort.java:29)
 at TestQuickSort.testFirstAsPivot(TestQuickSort.java:22)

The stacktrace looks much more readable now. Besides when using method references, you cannot close over variables as you definitely can with lambdas. It makes the code less error-prone.