Почему Collections.sort дважды вызывается Компаратором с теми же аргументами?

Question

Я использую пример, чтобы понять поведение компаратора в Java.

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 


    class HDTV { 
    private int size; 
    private String brand; 

    public HDTV(int size, String brand) { 
     this.size = size; 
     this.brand = brand; 
    } 

    public int getSize() { 
     return size; 
    } 

    public void setSize(int size) { 
     this.size = size; 
    } 

    public String getBrand() { 
     return brand; 
    } 

    public void setBrand(String brand) { 
     this.brand = brand; 
    } 
} 

class SizeComparator implements Comparator<HDTV> { 
    @Override 
    public int compare(HDTV tv1, HDTV tv2) { 
     int tv1Size = tv1.getSize(); 
     int tv2Size = tv2.getSize(); 
System.out.println("Comparing :: "+tv1.getBrand()+" AND : "+tv2.getBrand()); 
     if (tv1Size > tv2Size) { 
      return 1; 
     } else if (tv1Size < tv2Size) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

public class HelloWorld { 
    public static void main(String[] args) { 
     HDTV tv1 = new HDTV(55, "Samsung"); 
     HDTV tv2 = new HDTV(60, "Sony"); 
     HDTV tv3 = new HDTV(42, "Panasonic"); 

     ArrayList<HDTV> al = new ArrayList<HDTV>(); 
     al.add(tv1); 
     al.add(tv2); 
     al.add(tv3); 

     Collections.sort(al, new SizeComparator()); 
     for (HDTV a : al) { 
      System.out.println(a.getBrand()); 


     } 
     } 
    } 

Выход

Сравнение :: Sony и: Samsung
Сравнение :: Panasonic И: Sony
Сравнение :: Panasonic И: Sony
Сравнение :: Panasonic И: Samsung
Panasonic
Samsung
Sony

Почему это сравнение двух объектов Panasonic и Sony 2 раза подряд? Я не считаю, что это необходимо сделать.

Answer 1

Если это Java 7 или более поздняя версия, используется TimSort. TimSort запускается через вход и обнаруживает или собирает восходящие прогоны из 32 или более элементов (в этой реализации). См. countRunAndMakeAscending в исходном коде.

Проживает дольше, чем 32 осталось на месте. Запускает меньше 32, удваивая, делая двоичную вставку, сортируя последующие элементы в текущий прогон, пока не будет как минимум 32 элемента. См. binarySort в исходном коде.

(Слияние сортировки подхода выполняется только после пробегов> = 32 собранно. Поскольку ваш вход имеет только три элемента, весь сортировки выполняется с помощью двоичного вставки рода, и никакого слияния не будет сделано.)

Что нужно сделать countRunAndMakeAscending, так это обнаружить прогоны путем сравнения соседних элементов. Сначала он сравнивает Sony с Samsung, а затем Panasonic с Sony. Результатом является прогон длиной 2, [Samsung, Sony].

Далее, binarySort удлиняет этот пробег, беря следующий элемент Panasonic и вставляя его в нужное место. Бинарный поиск выполняется, чтобы найти это место.Средней точкой пробега 2 является местоположение 1, которое является Sony, поэтому сравнивает Panasonic с Sony. (Это повторное сравнение.) Panasonic меньше, чем Sony, поэтому следующее сравнение между Panasonic и Samsung, которое определяет правильную точку ввода. Теперь у нас пробег 3.

Поскольку весь ввод имеет длину 3, сортировка завершается после четырех сравнений.

Повторяющиеся сравнения происходят из-за того, что countRunAndMakeAscending и binarySort являются отдельными фазами сортировки, и бывает так, что последнее сравнение первой фазы совпадает с первым сравнением второй фазы.

Answer 2

Алгоритмы сортировки - сложная тема. Рассмотрим этот очень простой (но неэффективный) алгоритм.

Сравните первый элемент со вторым предметом. Следите за более высоким элементом и сравнивайте его со следующим элементом. Отслеживание наивысшего элемента до тех пор, пока вы не дойдете до конца списка, чтобы найти самый высокий элемент в списке. Поместите наивысший номер в новый список и удалите его из исходного списка.

Затем повторите предыдущие шаги, пока исходный список не станет пустым.

Поскольку вы просматриваете список несколько раз, вы можете в конечном итоге сравнить элемент соседа несколько раз. Возможно, даже последовательно на разных проходах.

Answer 3

Это зависит от алгоритма сортировки, от того, сколько раз он вызывает метод сравнения. Как только мы вызываем метод Collections.sort(), он переходит к реализации сортировки, используемой в Collections.sort().

В реализации Collections.sort() используется сортировка слиянием. Согласно Javadoc, только примитивные массивы сортируются с использованием Quicksort. Объектные массивы сортируются также с помощью Mergesort.