Bubble sort in functional style Java 8

Question

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

Answer 1

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

Answer 2

_{Algorithm with two nested loops: Bubble sort with step-by-step output}

---

Bubble sort with step-by-step output Java 8

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}