CODEWITHSUNDEEP
javasortingcomparator
Dave Bhavin
Dave Bhavin

Reputation: 97

How does comparator works internally?

It may sound trivial for you but I am having a hard time visualizing the comparator / array.sort. How can we sort a full array using only 2 arguments? How does it work internally?

for example- Input -[5,3,2,6,8,10,1], Output- [1,2,3,5,6,8,10] Which algo does it use internally? Which 2 objects does it compare at first? (5 compared to 3?) and then what are the next two objects? (5 compared to 2?) or (3 compared to 2)?

public static void main(String[] args) {
         Integer[] tring = new Integer[]{5,3,2,6,8,10,1};
       lol(tring);
       for(int i=0;i<tring.length;i++){
       System.out.println(tring[i]);
       }
    }
    
    public static void lol(Integer[] args) {
      Arrays.sort(args,(h1,h2)->h1-h2);
    }

Upvotes: 8

Views: 3102

Answers (2)

Christopher Oosthuizen
Christopher Oosthuizen

Reputation: 31

The comparator uses a sort called a TimSort

I personally do not feel qualified to explain the timsort algorithm, but I'm sure you can find plenty of explanations on google.

For the second part of your question, the way the comparator uses your two augments is to determine what order any two given values order should be.

So, for example, say if you wanted to sort [6,4] the comparator would use your function a-b and would then plug in the numbers 6 and 4 and get the 2 and because 2 is positive the sort knows that 6 needs to be behind 4. Which would result in [4,6].

Upvotes: 2

user4910279
user4910279

Reputation:

You can visualize the process like this.

Integer[] tring = new Integer[]  {5, 3, 2, 6, 8, 10, 1};
Comparator<Integer> comparator = (a, b) -> {
    System.out.println(Arrays.toString(tring) + " comparing " + a + " and " + b);
    return a.compareTo(b);
};
Arrays.sort(tring, comparator);
System.out.println(Arrays.toString(tring));

result:

[5, 3, 2, 6, 8, 10, 1] comparing 3 and 5
[5, 3, 2, 6, 8, 10, 1] comparing 2 and 3
[5, 3, 2, 6, 8, 10, 1] comparing 6 and 2
[2, 3, 5, 6, 8, 10, 1] comparing 6 and 3
[2, 3, 5, 6, 8, 10, 1] comparing 6 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 8 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 8 and 6
[2, 3, 5, 6, 8, 10, 1] comparing 10 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 10 and 8
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 6
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 3
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 2
[1, 2, 3, 5, 6, 8, 10]

Upvotes: 6

Related Questions