Какой вид использует Java Collections.sort (node)?

Question

Я думаю, что это MergeSort, то есть O (n log n).

Однако следующий вывод не совпадает:

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

Я сортирую список узлов из 4 узлов по порядковому номеру, и сортировка выполняет 6 сравнений. Я озадачен, потому что 6> (4 log (4)). Может кто-нибудь объяснить мне это?

P.S. Это слияние, но я все еще не понимаю свои результаты.

Спасибо за ответы всем. Спасибо, Том, за исправление моей математики.

Answer 1

O (n log n) не означает, что количество сравнений будет равно или меньше, чем n log n, просто то, что время будет масштабироваться пропорционально n log n. Попробуйте выполнить тесты с 8 или 16 узлами или 32 узлами и проверить время.

Answer 2

Вы отсортировали четыре узла, поэтому вы не получили сортировку слиянием; сортировка переключена на вставку сортировки.

В Java методы Arrays.sort () используют сортировку слиянием или настроенную быструю сортировку в зависимости от типов данных и для эффективности реализации переключаются на сортировку вставкой, когда сортируется менее семи элементов массива. (Википедия , акцент добавлен)

Arrays.sort используется косвенно классами Коллекций.

Недавно принятый отчет об ошибке указывает на то, что реализация Java в Sun будет использовать Python timsort в будущем: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

(монография Тимсорта, ссылка на которую приведена выше, заслуживает прочтения.)

Answer 3

Алгоритм A (n), который обрабатывает количество данных n, находится в O (f (n)) для некоторой функции f, если существуют две строго положительные константы C_inf и C_sup, такие что:

C_inf. f (n)

Две вещи на заметку:

• Фактические константы C могут быть любыми, и do зависит от относительной стоимости операций (в зависимости от языка, виртуальной машины, архитектуры или вашего фактического определения операции). На некоторых платформах, например, + и * имеют одинаковую стоимость, на других - более поздние на порядок медленнее.

• Количество, обозначаемое как "в O (f (n))", представляет собой ожидаемое число операций , основанное на некоторой, вероятно, произвольной модели данных, с которыми вы имеете дело. Например, если ваши данные почти полностью отсортированы, алгоритм сортировки слиянием будет в основном O (n), а не O (n. Log (n)).

Answer 4

Я написал кое-что, что вас может заинтересовать в алгоритме сортировки Java, и провел некоторые измерения производительности Collections.sort () . Алгоритм в настоящее время представляет собой сортировку слиянием с сортировкой вставок , как только вы доберетесь до определенного размера подсписков ( NB. Этот алгоритм очень вероятно изменится в Java 7 ).

Вы действительно должны принять обозначение Big O как показатель того, как алгоритм будет масштабироваться в целом; для конкретной сортировки точное время будет отличаться от времени, предсказанного этим вычислением (как вы увидите на моем графике, оба алгоритма сортировки, каждый из которых имеет разные характеристики производительности, и поэтому общее время сортировки составляет немного сложнее).

Тем не менее, в качестве приблизительного ориентира, каждый раз, когда вы удваиваете количество элементов, если вы умножите ожидаемое время на 2,2, вы не будете далеко от него. (Хотя на самом деле не имеет смысла делать это для очень маленьких списков из нескольких элементов.)