Как случайность введена в java-реализации Quicksort (DualPivotQuicksort)

Question

Я просматривал детали реализации класса DualPivotQuicksort в java.

Насколько алгоритм обеспокоен это, безусловно, является изменение Quicksort, хотя то, что не имеет смысла, это путь хаотичность вводится в выборе поворота и, следовательно, чтобы убедиться, что алгоритм работает в ожидается работает время O (n lg (n)).

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

https://arxiv.org/pdf/1403.6602

Answer 1

Вы не говорите , что Java-реализация, поэтому я предполагаю, что вы имеете в виду java.util.DualPivotQuicksort.

Этот класс не выбирает случайные стержни. Фактически, он выбирает 7 равноотстоящих потенциальных опорных элементов из подмассива, сортирует их и использует 3-й и 5-й пары (двойные).

Исключения:

• Небольшие массивы/Подмассивы сортируются при помощи вставки сортировки.
• Массивы byte сортируются с использованием сортировки.

(Примечание: это основано на реализации в Java 7/8)

Answer 2

В худшем случае для простого Реализация Quicksort происходит, когда вход уже отсортирован для вашей стратегической стратегии, например, если вы выбираете опорный элемент в качестве первого элемента подматрицы, вы получите наихудшее время выполнения, если ваши элементы уже в порядке. Поскольку мы часто сортируем массивы, которые «в основном отсортированы», чтобы начать с рандомизации выбора стержня, вы можете значительно приблизиться к ожидаемому времени выполнения на практике.

В идеале вы хотите выбрать стержень, который равномерно разделил бы вспомогательные проблемы, есть несколько вариантов выбора, из которых выбор случайного элемента - это только один. Другая, другая стратегия, которую я видел, отображает массив, собирающий 5 элементов, а затем используя медиану. (Edit: С другой ответ он выглядит DualPivotQuicksort на самом деле этот стиль с 7 точек отбора проб с последующим делением на три раздела Там нет случайности в этом подходе, а отбор проб.).

В конце концов, это все о нахождение наиболее быстрого или наиболее эффективного варианта для конкретной задачи. Если у вас есть дополнительная информация о базовой структуре того, что вы сортируете, вы можете адаптировать вариацию алгоритма, чтобы быть более успешной на ваших наборах данных. В библиотеке вы хотите быть быстрым, но также предсказуемым перед лицом «неправильного использования». Вот почему подход, который имеет хорошую производительность на уже отсортированном массиве, подобном этому, является хорошим кандидатом.