CODEWITHSUNDEEP
javasorting
CrazySabbath
CrazySabbath

Reputation: 1334

Collections Sort unexpected behaviour

Collections sort is not giving me the result I was expecting, or am I misreading the method?

List of Row objects is to be sorted:

public class Row {

    private int id;
    private boolean line;

    public Row(int id, boolean line) {
        this.id = id;
        this.line = line;
    }

    public boolean isLine() {
        return line;
    }

    @Override public String toString() {
        return "Row{" + "id=" + id + ", line=" + line + '}';
    }
}

Starting data:

[Row{id=0, line=true}, Row{id=1, line=false}, Row{id=2, line=true}, Row{id=3, line=false}]

Sorting code:

    Collections.sort(rows, new Comparator<Row>(){
        @Override public int compare(Row o1, Row o2) {
            if (!o1.isLine() && !o2.isLine()) return 0;
            if (o1.isLine()) {
                    return 1;
            } else {
                    return -1;
            }
        }
    });

Result: 

[Row{id=1, line=false}, Row{id=3, line=false}, Row{id=0, line=true}, Row{id=2, line=true}]

I was under the impresion that all objects with line=true should be at the start of the list, not the end.

If I slightly change Comporator implementation:

    Collections.sort(rows, new Comparator<Row>(){
        @Override public int compare(Row o1, Row o2) {
            if (!o1.isLine() && !o2.isLine()) return 0;
            if (o1.isLine()) {
                return -1;
            } else {
                return 1;
            }
        }
    });

Result:

[Row{id=2, line=true}, Row{id=0, line=true}, Row{id=1, line=false}, Row{id=3, line=false}]

All of objects with line=true can be found at the start of the list now, but they have switched places (id=0 should be first).

Expected sort result:

[Row{id=0, line=true}, Row{id=2, line=true}, Row{id=1, line=false}, Row{id=3, line=false}]

Upvotes: 1

Views: 196

Answers (3)

Anton Tupy
Anton Tupy

Reputation: 969

Your comparision is not symmetric and hence broken. Use inverted comparision implemented in Boolean class (please note minus in start of lambda body):

Collections.sort(rows, (o1, o2) -> -Boolean.valueOf(o1.isLine()).compareTo(o2.isLine()));

Upvotes: 0

davidxxx
davidxxx

Reputation: 131316

I was under the impresion that all objects with line=true should be at the start of the list, not the end.

Not really as this code :

  if (o1.isLine()) {
       return 1;
  }

means that o1 is superior to o2.
So object with isLine=true will happen to the end as default order is ascending.

All of objects with line=true can be found at the start of the list now, but they have switched places (id=0 should be first).

You never use the id in the comparator implementation.
It could never be considered.

To get :

[Row{id=0, line=true}, Row{id=2, line=true}, Row{id=1, line=false}, Row{id=3, line=false}]

You should add a getter in Row to retrieve the id. Then you should first sort by line=true and by id ASC.

 Collections.sort(rows, new Comparator<Row>(){
    @Override public int compare(Row o1, Row o2) {
        if (!o1.isLine() && !o2.isLine()) return 0;
        if (o1.isLine() && o2.isLine()) {
            return o1.getId() > o2.getId();
        }
        if (o1.isLine()) {
            return -1;
        } else {
            return 1;
        }
    }
 });

A more brief way to write that would be using Java 8 Comparator :

Comparator<Row> comparatorRow = Comparator.comparing(Row::isLine).reversed()
                                          .thenComparing(Row::getId);

As rows are already sorted by id and the sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort, you could compare only on isLine :

Comparator<Row> comparatorRow = Comparator.comparing(Row::isLine).reversed();

Upvotes: 3

CrazySabbath
CrazySabbath

Reputation: 1334

Summarising @Dukeling:

    Collections.sort(rows, new Comparator<Row>(){
        @Override public int compare(Row o1, Row o2) {
            return -Boolean.compare(o1.isLine(), o2.isLine());
        }
    });

This gives expected result.

Input:

[Row{id=0, line=true}, Row{id=1, line=false}, Row{id=2, line=true}, Row{id=3, line=false}]

Result:

[Row{id=0, line=true}, Row{id=2, line=true}, Row{id=1, line=false}, Row{id=3, line=false}]

Upvotes: 1

Related Questions