Skip to main content

Posts

Showing posts from February, 2015

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. Basic algorithm.Inline lambdas.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); …