Почему Arrays.sort - это алгоритм быстрой сортировки, а не другой алгоритм сортировки?

Question

Почему? Это быстрее или эффективнее?

Для систем с одним ядром мы можем использовать быструю сортировку. Что мы должны использовать в системах с двумя, четырьмя или восемью ядрами?

Answer 1

Быстрая сортировка имеет преимущество в том, что она полностью на месте, поэтому она не требует никакого дополнительного хранилища, в то время как сортировка слиянием (которая равна фактически используется Arrays.sort() для массивов объектов) и другие (все?) ГарантированныеАлгоритм O (n * log n) требует как минимум одну полную копию массива.Для программ, которые сортируют очень большие примитивные массивы, это означает потенциальное удвоение общего использования памяти.

Answer 2

Ответ есть у Джона Л. Бентли и М. Дугласа Макилроя «Разработка функции сортировки» , на которую ссылается функция сортировки.

Покупки по магазинам для лучшего качествамы обнаружили, что ксорт, написанный в Беркли в 1983 году, будет занимать квадратичное время для массивов, которые содержат несколько элементов, повторяющихся много раз, в частности массивы случайных нулей и единиц.Фактически, среди дюжины различных библиотек Unix мы не нашли qsort, который нельзя было бы легко привести к квадратичному поведению ;все они были получены из седьмого издания или из функции Беркли 1983 года.…

Не удалось найти достаточно хороший qsort, мы решили создать лучший.Алгоритм должен избегать экстремальных замедлений на разумных входах и должен быть быстрым на «случайных» входах.Он также должен быть эффективным в пространстве данных и пространстве кода.Сорт не обязательно должен быть стабильным;его спецификация не обещает сохранять порядок равных элементов.

Альтернативами были heapsort и mergesort, поскольку Java была создана в начале 1990-х годов.Mergesort менее желателен, поскольку требует дополнительного места для хранения.Heapsort имеет лучшую производительность в худшем случае (O(n log n) по сравнению с O(n^2)), но на практике работает медленнее.Таким образом, если вы можете контролировать производительность в худшем случае с помощью хорошей эвристики, настроенная быстрая сортировка - это путь.

Java 7 переключается на Timsort , который был изобретен в 1993 году (реализован вPython в 2002 году) и имеет худшую производительность O(n log n) и является стабильной сортировкой.

Answer 3

Быстрая сортировка имеет среднюю O (n log n) и O (n ^ 2) наихудшую производительность, что является наилучшим «средним случаем» для алгоритма сортировки, существуют другие алгоритмы сортировки, которые имеют такую ​​производительность, но быстрая сортировка имеет тенденцию работать лучше, чем большинство.

См .: http://en.wikipedia.org/wiki/Quicksort

Answer 4

Это настроенная быстрая сортировка. Если вы действительно заинтересованы, вы можете прочитать материал, упомянутый в документации.

Алгоритм сортировки представляет собой настроенную быструю сортировку, адаптированную из работ Джона Л. Бентли и М. Дугласа Макилроя «Разработка функции сортировки», Software-Practice and Experience, Vol. 23 (11) P. 1249-1265 (November 1993).

И вот небольшое объяснение - настроенная версия дает n * log (n) для многих наборов данных:

Этот алгоритм обеспечивает производительность n * log (n) для многих наборов данных, которые приводят к снижению быстродействия других быстрых сортировок до квадратичной производительности

Answer 5

По сравнению с быстрой сортировкой, в Mergesort меньше сравнений, но больше движущихся элементов.

В Java сравнение элементов обходится дорого, но перемещение элементов обходится дешево.Поэтому Mergesort используется в стандартной библиотеке Java для общей сортировки

. В C ++ копирование объектов может быть дорогостоящим, тогда как сравнение объектов часто является относительно дешевым.Таким образом, быстрая сортировка - это процедура сортировки, обычно используемая в библиотеках C ++.

ref: http://www.cs.txstate.edu/~rp44/cs3358_092/Lectures/qsort.ppt

Answer 6

Прежде всего Arrays.sort не только использует быструю сортировку, он использует несколько алгоритмов java1.6 и далее

Смотрите ниже код из класса массивов

/ ** * Сортирует указанный массив в порядке возрастания номеров. * *

Замечание по реализации: Алгоритм сортировки - быстрая сортировка с двумя точками * Владимир Ярославский, Джон Бентли и Джошуа Блох. Этот алгоритм * предлагает производительность O (n log (n)) для многих наборов данных, которые вызывают другие * быстрые сортировки для снижения до квадратичной производительности, и, как правило, * быстрее традиционных реализаций Quicksort. * * @param a массив для сортировки * / public static void sort (int [] a) { DualPivotQuicksort.sort (а); }

DualPivotQuicksort.sort(a); // This uses 5 algorithms internally depending upon dataset size 
do checkout the source code of Arrays class.

До Java 1.6 я думаю, что он использовал быструю сортировку с тремя алгоритмами для примитивных типов, таких как int и mergesort для объектов, и когда быстрая сортировка выполняла это, начинайте сортировку кучи, смотрите здесь для получения дополнительной информации http://cafe.elharo.com/programming/java-programming/why-java-util-arrays-uses-two-sorting-algorithms

Answer 7

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

Таким образом, сложность времени наихудшего случая всегда O (nlogn)

Answer 8

Поскольку с момента последнего ответа в этой теме прошло некоторое время, вот некоторые обновления ...

Это зависит от сложности и его соответствия размеру массива плюс вероятности, когда java исследовал эти алгоритмы и просто решил в зависимости от измерений и тестов.

Согласно JAVA JDK 1.8 DOCS самоочевидно, где он выбирает алгоритм, а не только один, но до четырех на выбор в соответствии с некоторыми пороговыми значениями ...

/**
     * If the length of an array to be sorted is less than this
     * constant, Quicksort is used in preference to merge sort.
     */
    private static final int QUICKSORT_THRESHOLD = 286;

    /**
     * If the length of an array to be sorted is less than this
     * constant, insertion sort is used in preference to Quicksort.
     */
    private static final int INSERTION_SORT_THRESHOLD = 47;

    /**
     * If the length of a byte array to be sorted is greater than this
     * constant, counting sort is used in preference to insertion sort.
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;

    /**
     * If the length of a short or char array to be sorted is greater
     * than this constant, counting sort is used in preference to Quicksort.
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

Ссылка Java DOC JDK 8

Это событие развилось, чтобы использовать параллельную сортировку Сортировка в Java

Java 8 поставляется с новым API - parallelSort - с сигнатурой, аналогичной Arrays.sort() API:

@Test
public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
    Arrays.parallelSort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

За кулисами parallelSort () он разбивает массив на различные подмассивы (согласно гранулярности в алгоритме параллельной сортировки). Каждый подмассив сортируется с помощью Arrays.sort () в разных потоках, так что сортировка может выполняться параллельно и окончательно объединяются в отсортированный массив.

Обратите внимание, что общий пул ForJoin используется для выполнения этих параллельных задач и затем объединения результатов.

Результат Arrays.parallelSort будет таким же, как и у Array. Конечно, это просто вопрос использования многопоточности.

Наконец, в Arrays.parallelSort также есть похожие варианты API Arrays.sort:

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

Резюме : Так как Java API развивается вместе с HardWare и программным обеспечением в целом есть больше пользы для многопоточности и настройки здесь и там на порогах и алгоритмах.

Answer 9

Arrays.sort () использует несколько алгоритмов сортировки в зависимости от размера и элементов в массиве.

• Вставка сортировки для небольших массивов
• Сортировка слияниемдля в основном отсортированных массивов
• высоконастраиваемая и адаптируемая быстрая сортировка с двумя и одним поворотом для всего остального

Итак, на практике мы видим, что быстрая сортировка очень быстрая для больших массивов примитивов,есть некоторые подводные камни, когда требуется адаптация к частично отсортированным массивам, когда сравнения между объектами медленны, для стабильной сортировки и т. д.

Answer 10

Это зависит от того, что вы хотите сделать. Проблема с обычной быстрой сортировкой состоит в том, что она иногда может быть в O (n²). Поэтому обычно вы можете использовать сортировку в куче, но в большинстве случаев быстрая сортировка выполняется быстрее.

Однако реализация Arrays.sort (...) использует «настроенную настроенную быструю сортировку, адаптированную Джоном Л. Бентли и М. Дугласом Макилрой [...]» (согласно документации JavaDoc). Этот алгоритм имеет некоторую встроенную оптимизацию, которая позволяет ему работать с O (n * log (n)), где обычная быстрая сортировка будет использовать O (n²).

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

iuiz