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.
Top comments (3)
Or simply
Collections.sort(cars, Comparator.comparing(car -> car.yearOfProduction));(I usually prefer inline sorting to avoid creation of unecessary copies in memory). Instead of using classes for data, I also recommend to get a look at records.You can also use a self-sorting data structure (ala heap) with a comparator to sort as you go. This gives O(log n) performance instead of O(n log n) for sorts on a separate data structure. In the standard library, this is a PriorityQueue.
You can also sort Java Arrays. Other collections like Set and Map can be sorted using similar techniques as in this post.