DEV Community

Cover image for Sorting in Java – how to, and how not to do it anymore
Pawel Pawlak
Pawel Pawlak

Posted on

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 + '\'' +
                '}';
    }
}
Enter fullscreen mode Exit fullscreen mode

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"));
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Collections.sort(cars);
cars.forEach(System.out::println);
Enter fullscreen mode Exit fullscreen mode

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'}
Enter fullscreen mode Exit fullscreen mode

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;
        }
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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

cars.sort(new HorsePowerComparator());
Enter fullscreen mode Exit fullscreen mode

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'}
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

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));  
Enter fullscreen mode Exit fullscreen mode

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());
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

Example of using this comparator looks like that:

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

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'}
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

Then we use it as simple as that:

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

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;
Enter fullscreen mode Exit fullscreen mode

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());
Enter fullscreen mode Exit fullscreen mode

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)

Collapse
 
dagnelies profile image
Arnaud Dagnelies • Edited

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.

Collapse
 
insouciantqualms profile image
InsouciantQualms

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.

Collapse
 
prsaya profile image
Prasad Saya

You can also sort Java Arrays. Other collections like Set and Map can be sorted using similar techniques as in this post.