CODEWITHSUNDEEP
javasortingcollectionsinterfacecomparable
David Prun
David Prun

Reputation: 8433

What determines ascending or descending order in Comparator / Comparable collection class?

I understand we can sort or order the objects, stored in Collection as per our requirement(s).

While I get deep understanding, I am not convinced by the fact that ascending and descending order of arrangement is achieved by (a - b) ->ascending or (b - a) -> descending where "a" and "b" are class members we chose to compare.

Example: 

public int compareTo(Student s) {
     return this.grade - s.grade; //ascending order 
    // return s.grade - this.grade; // descending order
}

What is logic behind ordering object elements? how "(this.grade - s.grade)" if positive 1 moves "this.grade" front and puts "s.grade" next in order, why not other way around? Who validates the compare result (+1, -1, 0) and then puts in ascending order or descending order respectively, is there any documentation that describes internal working of this part?

public class Student implements Comparable <Student>{
    String name;
    int grade;
    public Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }
    public int compareTo(Student s) {
         return this.grade - s.grade; //ascending order 
        // return s.grade - this.grade; // descending order
    }
    public String toString() {
        return this.name + ", " + this.grade;
    }
}

Please share, thank you much!

Edit:

I get the Java docs, my question is this:

sort these grades (13, 2)

Case ascending -> return this.grade - s.grade;

picture in my mind: 
compare (13, 2) , (13 - 2) > 0 so move 2 to front.
result -> 2, 13
------
Case descending -> return s.grade - this.grade;

picture in my mind: 
compare (2, 13) , (2 - 13) < 0 so move 13 to front.

result -> 13, 2

"How does this happen?" was my original question. I read the docs, still couldn't figure out.

Upvotes: 35

Views: 36046

Answers (3)

vlatkozelka
vlatkozelka

Reputation: 999

The Collections.sort() methods does .

Somewhere in the sort function in java, the fucntion compareTo(Comparable other) is called to determine how your comparable should be compared to the other comparable.

Lets say I have circle that I want to compare by diameter

public class Circle implements Comparable<Cricle> {
 int diameter;
 //constructor
 public int compareTo(Circle c){
  return this.diameter-c.diameter;
   }

now lets make an array of circles :

ArrayList<Circle> collection = new ArrayList;
collection.add(new Circle(10)); // and more circles

Now lets assume this is the sorting algorithm defined in Collection.sort() :

  Comparable tmp;
  for(int i=0;i<collection.size();i++){
   for(int j=i;j<collection.size();j++){
    if(collection.get(j).compareTo(collection.get(i)>0){
      //swap
      tmp=collection.get(i);
      collection.set(i,collection.get(j));
      collection.set(j,tmp);
     }
    }
   }

Java doesn't use bubble sort of course, but this is a rough example of how your implementation of compareTo will decide the oreder.

Upvotes: 2

Jay Modi
Jay Modi

Reputation: 245

@DavidPrun Good question. I have tried explaining this with an example.

(x,y) -> (2, 5)

Ascending Order (x.compareTo(y)):

if x.compareTo(y) == 1, then x > y , since y is smaller than x, you would have to move y in front of x.

2.compareTo(5) == 1 , Then don't move 5 in front of 2.

Descending Order (y.compareTo(x)):

if y.compareTo(x) == 1, then y > x , since y is greater than x, you would have to move y in front of x.

5.compareTo(2) == -1 , Move 5 in front of 2.

Basically, we will always move y in front of x, if the result of compareTo method is 1.

Upvotes: 10

dkatzel
dkatzel

Reputation: 31648

What is logic behind ordering object elements? how "(this.grade - s.grade)" if positive 1 moves "this.grade" front and puts "s.grade" next in order, why not other way around?

Using negative numbers to say "this is less than that", positive numbers to say "this is more than that" and 0 to say "these 2 things are equal" has been in many computer languages for 30+ years.

Who validates the compare result (+1, -1, 0) and then puts in ascending order / descending order respectively, is there any documentation that describes internal working of this part?

There are several internal classes that use the return value to reorder elements in arrays or collections including

Collections.sort() Arrays.sort() TreeSet

EDIT

To answer HOW that works you will have to look at the source code for each of the classes I listed above. Some of them are quite complicated to try to make the sorting as efficient as possible. But in general, it all boils down to code like this:

if( data[i].compareTo(data[j]) > 0 ){
   // swap data[i] and  data[j]
}

Upvotes: 22

Related Questions