about:drewcsillag

May 26, 2014 - 1 minute read - Java 8 functional programming

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.

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();
  }
}