Implement functional quicksort in Java


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

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;

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.


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 ().


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;

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

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

Recommended Posts

Implement functional quicksort in Java
Try functional type in Java! ①
Implement two-step verification in Java
Implement Basic authentication in Java
Implement math combinations in Java
2 Implement simple parsing in Java
Implement Email Sending in Java
Implement rm -rf in Java.
Implement XML signature in Java
3 Implement a simple interpreter in Java
Implement reCAPTCHA v3 in Java / Spring
Implement PHP implode function in Java
Try to implement Yubaba in Java
1 Implement simple lexical analysis in Java
How to implement date calculation in Java
How to implement Kalman filter in Java
Implement API Gateway Lambda Authorizer in Java Lambda
Partization in Java
Try to implement n-ary addition in Java
Changes in Java 11
Rock-paper-scissors in Java
How to implement coding conventions in Java
[Java] Functional interface
Implement something like a stack in Java
Pi in Java
FizzBuzz in Java
I tried to implement deep learning in Java
About Java functional interface
[java] sort in list
Read JSON in Java
Interpreter implementation in Java
Make Blackjack in Java
Rock-paper-scissors app in Java
NVL-ish guy in Java
Combine arrays in Java
"Hello World" in Java
Callable Interface in Java
Comments in Java source
Azure functions in java
Format XML in Java
Boyer-Moore implementation in Java
Hello World in Java
Use OpenCV in Java
webApi memorandum in java
Type determination in Java
Ping commands in Java
Various threads in java
Heapsort implementation (in java)
Zabbix API in Java
ASCII art in Java
Compare Lists in Java
Express failure in Java
Implement CustomView in code
Create JSON in Java
Date manipulation in Java 8
What's new in Java 8
Use PreparedStatement in Java
What's new in Java 9,10,11
Parallel execution in Java
Initializing HashMap in Java