Writing a comparator that sorts based on multiple fields

Question

I have 3 data fields, let's name them Field 1, Field 2, Field 3

Now let's say I have these values:

Field 1  Field 2  Field 3
    1       3        4
    2       3        3
    3       3        5
    4       2        5

How do I write a comparator that sorts such that I will have Field 1 in ascending order, and if Field 2is equal, then it will sort Field 3 by descending order. The result should be this:

Field 1  Field 2  Field 3
    1       3        5
    2       3        4
    3       3        3
    4       2        5

I am probably going to need to swap values around, but that is okay.

I have tried checking if `Field 2` is equal for two objects, and if they are, swap the values. Based on `Field 1` The problem is, the sorting algorithm used by the library doesn't seem to compare everything so I have some values that are still unsorted. — dtgee, Jan 18 '16 at 22:50
What kind of sorting library are you using? Is it accepting the standard Java [Comparator](https://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html)? — MJar, Jan 18 '16 at 22:53
Yes I am just using the java utils library and it is accepting the standard Comparator — dtgee, Jan 18 '16 at 23:12

GuiSim · Answer 1 · 2016-01-19T01:40:53.887

EDIT: I have misunderstood the problem. This solution sorts on Field 1 followed by Field 2 followed by Field 3. This is not what OP is looking for.

I suspect that you have a Java object that contains these three fields. I'll assume that they can be accessed via getters. I will also assume that your objects are stored in a List of some kind.

You have not specified which version of Java you are using so I'll go with a Java 8 solution. This could be used with earlier version of Java but it would be more verbose.

    List<MyObject> myObjects = Arrays.asList(new MyObject(1, 2, 3),
                                             new MyObject(0, 1, 2),
                                             new MyObject(1, 1, 1),
                                             new MyObject(1, 1, 0),
                                             new MyObject(1, 2, 1));
    List<MyObject> sortedList = myObjects.stream()
                                         .sorted(Comparator.comparing(MyObject::getField1)
                                                           .thenComparing(MyObject::getField2)
                                                           .thenComparing(MyObject::getField3))
                                         .collect(Collectors.toList());

    System.out.println(sortedList);

This program outputs

[0-1-2, 1-1-0, 1-1-1, 1-2-1, 1-2-3]

This solution uses Java 8 Stream API with the method sorted() which allows you to easily sort a Stream. The sort is achieved by using a Comparator which is a simple class that can determine which of two instances is "larger" than another.

Creating a Comparator that compares instances based on a field is very simple thanks to the Comparator.comparing() method. Comparing based on multiple fields is a simple process of chaining the returned Comparator using .thenComparing().

Java 8 method references are used to refer to field's getters.

Full code:

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class MyObject
{
    private int field1;
    private int field2;
    private int field3;

    public MyObject(int field1,
                    int field2,
                    int field3)
    {
        this.field1 = field1;
        this.field2 = field2;
        this.field3 = field3;
    }

    public int getField1()
    {
        return field1;
    }

    public int getField2()
    {
        return field2;
    }

    public int getField3()
    {
        return field3;
    }

    @Override
    public String toString()
    {
        return field1 + "-" + field2 + "-" + field3;
    }

    public static void main(String[] args)
    {
        List<MyObject> myObjects = Arrays.asList(new MyObject(1, 2, 3),
                                                 new MyObject(0, 1, 2),
                                                 new MyObject(1, 1, 1),
                                                 new MyObject(1, 1, 0),
                                                 new MyObject(1, 2, 1));
        List<MyObject> sortedList = myObjects.stream()
                                             .sorted(Comparator.comparing(MyObject::getField1)
                                                               .thenComparing(MyObject::getField2)
                                                               .thenComparing(MyObject::getField3))
                                             .collect(Collectors.toList());

        System.out.println(sortedList);
    }
}

Simply create a `Comparator` that compares based on field1 and if they are equal, compares based on field2 and if they are equal compares based on field3. This answer you be a great starting point: http://stackoverflow.com/questions/2839137/how-to-use-comparator-in-java-to-sort — GuiSim, Jan 18 '16 at 22:59
But `Field 1` doesn't have to be equal. `Field 1` is the main sorting priority. Only if after we sorted by `Field 1` and we see that `Field 2` is equal, we should sort those objects equal in `Field 2`s by descending `Field 3` — dtgee, Jan 18 '16 at 23:07
Ok then, I have misunderstood your problem. I will edit my answer. — GuiSim, Jan 19 '16 at 01:39

score 1 · Answer 2 · answered Jan 18 '16 at 23:18

I would do this in two parts. Part 1 would be to sort based on Field 1.

Part 2 would involve creating a map (HashMap) with the values of Field 2 as the keys mapping to a binary heap (PriorityQueue) of the Field 3 values, sorted in reverse order. I would then iterate though the original array and replace Field 3 with the element take form the top of the Field 2 heap.

score 0 · Answer 3 · answered Jan 19 '16 at 22:36

Ok after reading your reply to the earlier answer, I think you are after a two pass approach. First you want to sort the list of objects by the first field. Then you want to go back through the collection and if two items have the same field two, we sort them by field three.

So this is easiest to do by sorting the collection twice using two different comparators, the first to sort by field one:

@Override
public int compare(MyObject o1, MyObject o2) {
    return Integer.compare(o1.getFieldOne(), o2.getFieldOne());
}

And the second that sorts by field three only when field two is equal

    @Override
    public int compare(MyObject o1, MyObject o2) {
        int secondFieldComparison = Integer.compare(o1.getFieldTwo(), o2.getFieldTwo());
        if (secondFieldComparison == 0) {
            return Integer.compare(o1.getFieldThree(), o2.getFieldThree());
        } else {
            return 0;
        }
    }

Writing a comparator that sorts based on multiple fields

3 Answers3