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