So I want to sort this numbers in list from smallest to biggest. In compare method it look like it is sorting desceding at first, but after the compare method is done with sorting, list is ascended sorted as I was expecting.
Main:
public class Main {
public static void main(String[] main){
Integer[] numbers = {3,2,6,1};
List<Integer> list = Arrays.asList(numbers);
Collections.sort(list,new SortNumbers());
System.out.println(list);
}
}
SortNumbers class:
import java.util.Comparator;
public class SortNumbers implements Comparator<Integer> {
@Override
public int compare(Integer i1, Integer i2) {
if(i1 > i2){
System.out.println(i1 + " " + i2 + " -> returns 1");
return 1;
}else{
System.out.println(i1 + " " + i2 + " -> returns -1");
return -1;
}
}
}
Output:
2 3 -> returns -1 6 2 -> returns 1 6 3 -> returns 1 1 3 -> returns -1 1 2 -> returns -1 [1, 2, 3, 6]
And also I dont understand why was method comparing 1 and 3 because they are never next to each other.
Advertisement
Answer
When you call sort, Java internally uses Tim sort to sort the list. (Note that the actual used sorting method is not a requirement by the language, future updates for Java may chance it even in minor updates)
Since your list is smaller than the typical threshold used for Tim sorts merge vs insertion behavior, it Tim sort delegates sorting your list to insertion sorting.
Java then uses a variant of insertion sort that tries to minimize the comparisons done by using a binary search to find the index.
It starts with:
Sorted: [] Unsorted: [3,2,6,1]
It picks the first number, no further checks are done, sine a list of 1 is always sorted
Sorted: [3] Unsorted: [2,6,1]
It then looks at the second number, and sees that it is smaller, so it puts it before the 3. One observation here, is that it puts the item under test in the A variable, note that this is an implementation detail. Because the compare function return -1, it knows the item has to be inserted to the left of the checked element)
Comparisons done: (2, 3) => -1 Sorted: [2,3] Unsorted: [6,1]
Now that we have 2 numbers, we either have to pick the first or second one and hope it was the best choose, java always compares it with the first number
Comparisons done: (6, 2) => 1, (6, 3) => 1 Sorted: [2, 3, 6] Unsorted: [1]
Now we are the last item, we first call the compare function between 1 and 3. We either get lucky and it returns 0, or we have to do 1 call more to see where the item belongs
Comparisons done: (1, 3) => -1, (1, 2) => -1 Sorted: [1, 2, 3, 6] Unsorted: []
We are done with the algorithm