Sorting in Java – how to, and how not to do it anymore

Comments and articles about sorting in java are plenty over the internet, this one will be so called a summary of the examples I have seen in my developers carrier. It will not cover all the basics, but will try to show you some of the possibilities, from the one that I would try to avoid currently, to the ones that I prefer to use now.

For all testing purpose we will use Car class

package com.developersmill.sorting.interfaceimpl;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public final class Car{
    private final int yearOfProduction;
    private final int horsePower;
    private final String brand;
    private final String model;
    public Car(int yearOfProduction, int horsePower, 
               String brand, String model) {
        this.yearOfProduction = yearOfProduction;
        this.horsePower = horsePower;
        this.brand = brand;
        this.model = model;
    }
    @Override
    public String toString() {
        return "Car{" +
                "yearOfProduction=" + yearOfProduction +
                ", horsePower=" + horsePower +
                ", brand='" + brand + '\'' +
                ", model='" + model + '\'' +
                '}';
    }
}

and this example list:

final List<Car> cars = Arrays.asList(
                new Car(1989, 60,"Toyota", "Yaris"),
                new Car(2010, 90,"Mazda", "3"),
                new Car(2004, 110,"Toyota", "Corolla"),
                new Car(1999, 150,"BMW", "5"),
                new Car(2010, 60,"Renault", "Clio"),
                new Car(2016, 70,"Renault", "Twingo"),
                new Car(2021, 190,"Skoda", "Superb"));

How not to implement sorting this days

1. Implementing Comparable interface

First solution, and the oldest one I know, is to implement an interface Comparable, and provide the implementation of the compareTo method in the class we want to sort. We are going to do that in the class Car.

public final class Car implements Comparable<Car> {
    ....
    @Override
    public int compareTo(Car car) {
        return yearOfProduction - car.yearOfProduction;
    }
}

To test our solution simply call sort method on the Collections class

Collections.sort(cars);
cars.forEach(System.out::println);

Result is:

Car{yearOfProduction=1989, horsePower=60, brand='Toyota', model='Yaris'}
Car{yearOfProduction=1999, horsePower=150, brand='BMW', model='5'}
Car{yearOfProduction=2004, horsePower=110, brand='Toyota', model='Corolla'}
Car{yearOfProduction=2010, horsePower=90, brand='Mazda', model='3'}
Car{yearOfProduction=2010, horsePower=60, brand='Renault', model='Clio'}
Car{yearOfProduction=2016, horsePower=70, brand='Renault', model='Twingo'}
Car{yearOfProduction=2021, horsePower=190, brand='Skoda', model='Superb'}

This solution have two main problems:

it forces to compare only base on one specific field, that can not be changed.
it requires changes in the class
it modifies the input object – mutability

2. Provide different implementations of comparators with new classes

Next solution is about providing new classes that implements the Comparator interface each time we want to change the way our data is sorted.

For example we want to sort once using the year of production and once using the horse power. We have to implement two classes for that:

static class YearComparator implements Comparator<Car>{
        @Override
        public int compare(Car o1, Car o2) {
            return o1.yearOfProduction - o2.yearOfProduction;
        }
}
static class HorsePowerComparator implements Comparator<Car>{
        @Override
        public int compare(Car o1, Car o2) {
            return o1.horsePower - o2.horsePower;
        }
}

Each class implements the Comparator class and provides the implementation of the the compare method. Car class interface Comparator is not needed anymore. Now tests our code:

Collections.sort(cars, new YearComparator()); // sort data using the year of production like in the first example
Collections.sort(cars, new HorsePowerComparator()); // new way of sorting
cars.forEach(System.out::println);

It can also be directly used using the list of cars itself:

cars.sort(new HorsePowerComparator());

Result is:

Car{yearOfProduction=1989, horsePower=60, brand='Toyota', model='Yaris'}
Car{yearOfProduction=2010, horsePower=60, brand='Renault', model='Clio'}
Car{yearOfProduction=2016, horsePower=70, brand='Renault', model='Twingo'}
Car{yearOfProduction=2010, horsePower=90, brand='Mazda', model='3'}
Car{yearOfProduction=2004, horsePower=110, brand='Toyota', model='Corolla'}
Car{yearOfProduction=1999, horsePower=150, brand='BMW', model='5'}
Car{yearOfProduction=2021, horsePower=190, brand='Skoda', model='Superb'}

This solution is much better, but still not perfect. Class do not have to implement the interface, so we do not have to change it at all. We only need to provide the implementation of Comparator classes for each case we want to use.

3. Using Java streams with mutable list

Next example shows that sorting can be also done quite easily with the use of Java 8 API.

Our goal again, is to sort the list of cars, by their year of production. To do so we are going to use the sorted method with the Comparator parameter. It can be done in several ways. First one below shows implementation of Comparator inline, in code as a lambda expression.

List<Car> sorted = new ArrayList<>();
cars.stream().sorted((car1, car2) -> car1.yearOfProduction - car2.yearOfProduction)
             .forEach(car -> sorted.add(car));

Second example shows use the of already implemented class YearComparator:

List<Car> sorted = new ArrayList<>();
cars.stream().sorted(new YearComparator())
             .forEach(car -> sorted.add(car));

Those two examples looks much more cleaner that the ones shown in the points 1 and 2, but there is one problem in there – mutability! If we decide to switch to concurrent iteration we will be forced to deal with the thread-safety problems.

How to correctly implement sorting this days

1. Using the Java 8 streams with collect method

All examples that were shown in the point 3 in this article can be fixed by using the collect terminal method. Lets change the last example that was using the ‘new YearComparator()‘ comparator:

List<Car> sorted = cars.stream()
                .sorted(new YearComparator())
                .collect(Collectors.toList());

This will solve our problems with the concurrent modifications issues, we do not longer modify existing object.

2. Functional style with Comparator

Instead of implementing small classes like e.g. YearComparator we can provide its implementation using the functional style of programming introduced in Java 8. This could look like that:

Comparator<Car> years = (car1, car2) -> car1.yearOfProduction - car2.yearOfProduction;

Example of using this comparator looks like that:

List<Car> sorted = cars.stream().sorted(years)
                .collect(Collectors.toList());

Final results look like that now:

Car{yearOfProduction=1989, horsePower=60, brand='Toyota', model='Yaris'}
Car{yearOfProduction=1999, horsePower=150, brand='BMW', model='5'}
Car{yearOfProduction=2004, horsePower=110, brand='Toyota', model='Corolla'}
Car{yearOfProduction=2010, horsePower=60, brand='Renault', model='Clio'}
Car{yearOfProduction=2010, horsePower=90, brand='Mazda', model='3'}
Car{yearOfProduction=2016, horsePower=70, brand='Renault', model='Twingo'}
Car{yearOfProduction=2021, horsePower=190, brand='Skoda', model='Superb'}

3. Functional style with Function and Comparing

When Java 8 was introduced Comparator interface was filled with plenty of static methods. One of those is comparing. It allows to use the Function method as a parameter to use its logic, to create new Comparator. Best would be to show it using an example.

Imagine we have simple Car POJO class, with no Comparable interface implemented. We want again to sort with the year property. We defined our lambda, to say on what parameter we want to perform sorting:

Function<Car, Integer> year = car -> car.yearOfProduction;

Then we use it as simple as that:

List<Car> sorted = cars.stream()
                .sorted(Comparator.comparing(year))
                .collect(Collectors.toList());

This will give us the results we want. We can even go a bit further and define second lambda to sort with the use of horse power and combine those two sorting together!

Function<Car, Integer> horsePower = car -> car.horsePower;

Sorting first with the year and then with the horsepower would look like that:

List<Car> sorted = cars.stream()        
     .sorted(Comparator.comparing(year)
     .thenComparing(horsePower))
     .collect(Collectors.toList());

Conclusion

There are various way we can sort our data. I myself find using Java 8 API to have most advantages:

not mutable data – we never change data we are sorting, always create new results.
not forced to change the class we are sorting (e.g. implementing Comparable interface).
provide simple and easy to read lambda definitions.
combine several ways of sorting.

Blog

Sorting in Java – how to, and how not to do it anymore

Pawel Pawlak

How not to implement sorting this days

How to correctly implement sorting this days

Join Our Newsletter. No Spam, Only the good stuff.

Related