about:drewcsillag

Musings of a programmer, musician and Christian.

Quicksort and Java 8

In looking at functional languages, I’ve often been impressed with the clarity of implementations of Quicksort. Now that Java 8 includes lambdas, we can now do one that, while not as nice as an implementation in, say Haskell, is still quite nice.

While I wouldn’t use the below code in production, as it’s choice of pivot point is naive and would go kaboom on a large sorted list from stack exhaustion, it is a nice illustration of the utility and clarity that Java 8’s lambdas when mixed with Guava functional stuff give.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import com.google.common.base.Predicate;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;

import java.util.Comparator;
import static com.google.common.collect.Iterables.filter;
import static com.google.common.collect.Iterables.get;
import static com.google.common.collect.Iterables.skip;
import static com.google.common.collect.Iterables.size;
import static com.google.common.base.Predicates.not;

public class FunctionalQuicksort {
  public static <T> Iterable<T> quicksort(Iterable<T> input, final Comparator<T> comparator) {
    if (size(input) <= 1) {
      return input;
    }
    final T pivot = get(input, 0);
    final Iterable<T> rest = skip(input, 1);
    final Predicate<T> lessThan = el -> comparator.compare(el, pivot) < 0;
    return ImmutableList.<T>builder()
        .addAll(quicksort(filter(rest, lessThan), comparator))
        .add(pivot)
        .addAll(quicksort(filter(rest, not(lessThan)), comparator))
        .build();
  }
}

Comments