How would you implement the following Bubble Sort algorithm in a functional (Java 8) way?
public static final <T extends Comparable<T>> List<T> imperativeBubbleSort(List<T> list) {
int len = list == null ? 0 : list.size();
for (int j = len - 1; j > 0; j--) {
for (int k = 0; k < j; k++) {
if (list.get(k + 1).compareTo(list.get(k)) < 0) {
list.add(k, list.remove(k + 1));
}
}
}
return list;
}
It would depend on what you mean by functional. If you mean just passing around functions as first class objects, then you should change your method signature to be:
public static final <T> List<T> imperativeBubbleSort(List<T> list, Comparator<T> comparisonFunction)
This way the comparison logic can be supplied as an argument.
If you mean going fully functional and not at all procedural, then I would call it an anti-pattern. Despite what you might hear, Java 8 does not fully support functional programming. A key feature that it is missing is tail-call optimization. Without it, the sort of loop-less programming that defines functional programming is likely to crash your JVM for relatively small values.
More information about tail call optimizations and the JVM can be found here: http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044
Algorithm with two nested loops: Bubble sort with step-by-step output
You can replace two nested loops with two nested streams. The inner stream passes through the list, compares adjacent elements and returns the count of swaps. And the outer stream repeats passes until there is nothing left to swap in the inner stream.
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
Collections.addAll(list, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1);
bubbleSort8(list);
}
public static void bubbleSort8(List<Integer> list) {
// counters: 0-passes, 1-swaps
int[] counter = new int[2];
IntStream.iterate(0, i -> i + 1)
// output the beginning of the pass and increase the counter of passes
.peek(i -> System.out.print((i==0?"<pre>":"<br>")+"Pass: "+counter[0]++))
// repeat the passes through the list until
// all the elements are in the correct order
.anyMatch(i -> IntStream
// pass through the list and
// compare adjacent elements
.range(0, list.size() - 1)
// if this element is greater than the next one
.filter(j -> list.get(j) > list.get(j + 1))
// then swap them
.peek(j -> Collections.swap(list, j, j + 1))
// output the list and increase the counter of swaps
.peek(j -> System.out.print(outputSwapped8(list,j,j+1,counter[1]++)))
// if there are no swapped elements at the
// current pass, then this is the last pass
.count() == 0);
// output total
System.out.print("<br>Total: Passes=" + counter[0]);
System.out.println(", swaps=" + counter[1] + "</pre>");
}
static String outputSwapped8(List<Integer> list, int e1, int e2, int counter) {
return IntStream.range(0, list.size())
.mapToObj(i -> i == e1 || i == e2 ?
// swapped elements are in bold
"<b>" + list.get(i) + "</b>" :
// other elements
"" + list.get(i))
.collect(Collectors.joining(" ", "<br>", " | " + counter));
}
Output:
Pass: 0
9 10 8 7 6 5 4 3 2 1 | 0
9 8 10 7 6 5 4 3 2 1 | 1
9 8 7 10 6 5 4 3 2 1 | 2
9 8 7 6 10 5 4 3 2 1 | 3
9 8 7 6 5 10 4 3 2 1 | 4
9 8 7 6 5 4 10 3 2 1 | 5
9 8 7 6 5 4 3 10 2 1 | 6
9 8 7 6 5 4 3 2 10 1 | 7
9 8 7 6 5 4 3 2 1 10 | 8
Pass: 1
8 9 7 6 5 4 3 2 1 10 | 9
8 7 9 6 5 4 3 2 1 10 | 10
8 7 6 9 5 4 3 2 1 10 | 11
8 7 6 5 9 4 3 2 1 10 | 12
8 7 6 5 4 9 3 2 1 10 | 13
8 7 6 5 4 3 9 2 1 10 | 14
8 7 6 5 4 3 2 9 1 10 | 15
8 7 6 5 4 3 2 1 9 10 | 16
Pass: 2
7 8 6 5 4 3 2 1 9 10 | 17
7 6 8 5 4 3 2 1 9 10 | 18
7 6 5 8 4 3 2 1 9 10 | 19
7 6 5 4 8 3 2 1 9 10 | 20
7 6 5 4 3 8 2 1 9 10 | 21
7 6 5 4 3 2 8 1 9 10 | 22
7 6 5 4 3 2 1 8 9 10 | 23
Pass: 3
6 7 5 4 3 2 1 8 9 10 | 24
6 5 7 4 3 2 1 8 9 10 | 25
6 5 4 7 3 2 1 8 9 10 | 26
6 5 4 3 7 2 1 8 9 10 | 27
6 5 4 3 2 7 1 8 9 10 | 28
6 5 4 3 2 1 7 8 9 10 | 29
Pass: 4
5 6 4 3 2 1 7 8 9 10 | 30
5 4 6 3 2 1 7 8 9 10 | 31
5 4 3 6 2 1 7 8 9 10 | 32
5 4 3 2 6 1 7 8 9 10 | 33
5 4 3 2 1 6 7 8 9 10 | 34
Pass: 5
4 5 3 2 1 6 7 8 9 10 | 35
4 3 5 2 1 6 7 8 9 10 | 36
4 3 2 5 1 6 7 8 9 10 | 37
4 3 2 1 5 6 7 8 9 10 | 38
Pass: 6
3 4 2 1 5 6 7 8 9 10 | 39
3 2 4 1 5 6 7 8 9 10 | 40
3 2 1 4 5 6 7 8 9 10 | 41
Pass: 7
2 3 1 4 5 6 7 8 9 10 | 42
2 1 3 4 5 6 7 8 9 10 | 43
Pass: 8
1 2 3 4 5 6 7 8 9 10 | 44
Pass: 9
Total: Passes=10, swaps=45
See also: Bubble sort algorithm for a linked list
I don't think Java 8 will provide much help in this case to write bubble sort in a functional style.
For example this implementation implementation of Bubble sort in Haskell can be simulated in Java as follows. It's more functional as it uses recursion instead of iteration, but still Java 8 lacks features such as pattern matching, list concatenation, etc to express the algorithms in a more functional style.
public static final <T extends Comparable<T>> List<T> functionalBubbleSort(List<T> list) {
for (int i = 0; i < list.size(); i++) {
list = onePassSort(list);
}
return list;
}
public static final <T extends Comparable<T>> List<T> onePassSort(List<T> list) {
if (list.size() == 0 || list.size() == 1) {
return list;
} else {
T first = list.get(0);
T second = list.get(1);
if (first.compareTo(second) < 0) {
return merge(first, onePassSort(list.subList(1, list.size())));
} else {
return merge(second, onePassSort(merge(first, list.subList(2, list.size()))));
}
}
}
public static <T> List<T> merge(T head, List<T> tail) {
List<T> result = new ArrayList<>();
result.add(head);
result.addAll(tail);
return result;
}
Shortest way I could think of is following. Where listForBubbleSort is input, and bubbleSorted is the output.
List<Integer> listForBubbleSort = Arrays.asList(5, 4, 3, 7, 6, 9, 11, 10, 21);
final List<Integer> copiedList = new ArrayList<>(listForBubbleSort);
copiedList.add(Integer.MAX_VALUE);
final List<Integer> bubbleSorted = new ArrayList<>();
copiedList.stream().reduce((c, e) -> {
if (c < e) {
bubbleSorted.add(c);
return e;
} else {
bubbleSorted.add(e);
return c;
}
});
System.out.println(bubbleSorted); // [4, 3, 5, 6, 7, 9, 10, 11, 21]
I still feel that, if we could create a custom collector and just pass the collector to the collect of stream that would be great. Like we pass collect(toList()) to the stream. But still learning Java 8, so need more time to create the same.
If anyone has already created a custom collector for the same please share.
I got a plausible approach:
@SuppressWarnings("unchecked")
public static final <T extends Comparable<T>> List<T> declarativeBubbleSort(final List<T> list) {
List<T> result = new ArrayList<>(list);
int len = result.size();
Function<Function<Object, Object>, IntConsumer> consumer =
recur -> length -> IntStream.range(0, length)
.filter(i -> IntStream.range(0, len - i - 1)
.filter(j -> result.get(j + 1).compareTo(result.get(j)) < 0)
.mapToObj(j -> {
T swap = result.remove(j + 1);
result.add(j, swap);
return swap;
}).count() > 0)
.max().ifPresent(IntConsumer.class.cast(recur.apply(Function.class.cast(recur))));
consumer.apply(Function.class.cast(consumer)).accept(len);
return result;
}
I know I'm still being a bit imperative, but for this kind of sort, I find it hard to do it completely declarative in Java and not to penalize performance.
If you want to be parallel, then:
@SuppressWarnings("unchecked")
public static final <T extends Comparable<T>> List<T> declarativeParallelBubbleSort(final List<T> list) {
List<T> result = new ArrayList<>(list);
int len = result.size();
Function<Function<Object, Object>, IntConsumer> consumer =
recur -> length -> IntStream.range(0, length)
.filter(i -> IntStream.range(0, len - i - 1)
.filter(j -> result.get(j + 1).compareTo(result.get(j)) < 0)
.parallel()
.mapToObj(j -> {
synchronized (result) {
T swap = result.remove(j + 1);
result.add(j, swap);
return swap;
}
}).count() > 0)
.max().ifPresent(IntConsumer.class.cast(recur.apply(Function.class.cast(recur))));
consumer.apply(Function.class.cast(consumer)).accept(len);
return result;
}
Simplified version using Java 8 api:
public static int[] bubbleSort(int[] array) {
BiConsumer<int[], Integer> swapValueIf = (a, j) -> {
if (a[j] > a[j + 1]) {
int temp = a[j];
array[j] = a[j + 1];
array[j + 1] = temp;
}
};
IntStream.range(0, array.length - 1)
.forEach(i -> IntStream.range(0, array.length - 1)
.forEach(j -> swapValueIf.accept(array, j)));
return array;
}
