Implement functional quicksort in Java

Introduction

I implemented quicksort using lambda expression and Stream in Java. The target audience for this article is:

--People who have mastered Scala --People who want to get started with Java's functional features

lambda expression

A lambda expression can be written in the form (argument)-> return value, and the function can be called with the apply method.

import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<String, String> addHoge = (final String str) -> str + "hoge";
        System.out.println(addHoge.apply("fuga"));
    }
}

Also, if you want to write multiple expressions, you can use blocks.

import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<String, String> addHoge = (final String str) -> {
            String hoge = "hoge";
            return str + hoge;
        };
        System.out.println(addHoge.apply("fuga"));
    }
}

Stream Stream is a class that supports functional operations on collection elements. Stream can be used by calling the stream () method of the collection class.

If you write a program that displays multiples of 2 using stream (), it will be as follows.

Java

Arrays.asList(3, 21, 34, 0).stream().filter(n -> n % 2 == 0).forEach(System.out::println);

In Scala it looks like this: Compared to Java, the code is simpler because you don't have to write stream ().

Scala

List(3, 21,34, 0).filter(_ % 2 == 0).foreach(println)

Source code (Scala)

Before implementing quicksort in Java, here is the code implemented in Scala. The quicksort pivot is specified at the beginning of the array.

object Main extends App {
    println(quickSort(List(3, 21, 34, 0, -30, 55, 10)))
    
    def quickSort(nums: List[Int]): List[Int] = {
      nums.headOption.fold(List[Int]()){ pivot =>
        val left = nums.filter(_ < pivot)
        val right = nums.filter(pivot < _)
        quickSort(left) ++ List(pivot) ++ quickSort(right)
      }
    }
}

Source code (Java)

The following is an implementation of quicksort in Java.

Compared to Scala code, I'm overwhelmed by the amount of Java code, but I think the logic itself has almost the same implementation.

The only difference in logic is the fold method. There are places in Scala code that use the fold method, but there is no fold method in the Java Optional type (Option type in Scala). Instead, the map method and the OrElseGet method (getOrElse method in Scala) are used in combination.

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import static java.util.stream.Collectors.toList;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        final List<Integer> nums = Arrays.asList(3, 21, 34, 0, -30, 55, 10);
        final List<Integer> sorted = quickSort(nums);
        System.out.println(sorted.toString());
    }

    private static List<Integer> quickSort(final List<Integer> nums) {
        return nums.stream().findFirst().map((final Integer pivot) -> {
            final List<Integer> left = nums.stream().filter(n -> n < pivot).collect(toList());
            final List<Integer> middle = Collections.singletonList(pivot);
            final List<Integer> right = nums.stream().filter(n -> pivot < n).collect(toList());
            return Stream.of(quickSort(left), middle, quickSort(right)).flatMap(Collection::stream).collect(toList());
        }).orElseGet(Collections::emptyList);
    }
}