Подтвердить что ты не робот

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Quicksort имеет среднее значение O (n log n) и O (n ^ 2), то есть лучший "средний случай", который может быть алгоритмом сортировки, существуют другие алгоритмы сортировки, которые имеют эту производительность, но quicksort имеет тенденцию чтобы работать лучше, чем большинство.

Смотрите: http://en.wikipedia.org/wiki/Quicksort

Ответ 2

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

Ответ 3

Ответ есть у Джона Л. Бентли и М. Дугласа Макилройса "Проектирование функции сортировки", которую цитирует функция сортировки.

В поисках лучшей qsort мы обнаружили, что qsort, написанный в Беркли в 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) и является стабильной сортировкой.

Ответ 4

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

Алгоритм сортировки - это настроенная быстродействующая сортировка, адаптированная из Jon L. Bentley и M. Douglas McIlroy "Engineering a Sort Function", Software-Practice and Experience, Vol. 23 (11) P. 1249-1265 (ноябрь 1993 г.).

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

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

Ответ 5

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

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

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

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

Ответ 6

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

См. ниже код класса Arrays

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

Замечание по реализации: Алгоритм сортировки представляет собой Double-Pivot Quicksort    * Владимир Ярославский, Джон Бентли и Джошуа Блох. Этот алгоритм    * предлагает O (n log (n)) производительность на многих наборах данных, которые вызывают другие    * quicksorts деградируют до квадратичной производительности и обычно    * быстрее, чем традиционные (однопоточные) реализации Quicksort.    *    * @param массив, который нужно отсортировать    */   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 для объектов, и когда quick sort out выполняет его запуск, куча сортировки, см. здесь для получения более подробной информации http://cafe.elharo.com/programming/java-programming/why-java-util-arrays-uses-two-sorting-algorithms

Ответ 7

Quicksort быстрее всего O(n log(n)), поэтому Sun, вероятно, использовал это как хорошую метрику.

Ответ 8

QuickSort - общий алгоритм сортировки. Это достаточно быстро, за исключением случаев, когда данные для сортировки уже находятся в обратном порядке. Он также эффективен в космосе.

Ответ 9

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

Однако в реализации Arrays.sort(...) используется "настроенная настраиваемая быстродействующая сортировка, адаптированная из Jon L. Bentley и M. Douglas McIlroy [...]" (согласно документации JavaDoc). У этого алгоритма есть некоторая сборка оптимизаций, которая позволяет ему работать с O (n * log (n)), где обычный quicksort будет использовать O (n²).

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

iuiz

Ответ 10

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

  • Сортировка вставки для небольших массивов
  • Объединить сортировку для отсортированных массивов
  • Высоко настраиваемая и адаптируемая двухполюсная и одиночная быстродействующая сортировка для всего остального.

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

Ответ 11

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

Это зависит от сложности и его соответствия размеру массива плюс вероятность, когда 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 - с аналогичной сигнатурой для API Arrays.sort():

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

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

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

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

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

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

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

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

Ответ 12

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

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