Что такое Детерминированный Quicksort?

В общем, алгоритм сортировки является «детерминированным», если он последовательно сортирует элементы в одном и том же порядке каждый раз. Учитывая набор записей для сортировки по id (asc):

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

, тогда алгоритм сортировки может возвращать Censu, Cikk, Marju, Lonzu или Censu, Cikku, Lonzu, Marju в качестве правильных сортировок. Детерминированная сортировка всегда возвращает один и тот же порядок. Это не всегда так. В случае быстрой сортировки можно получить более высокую среднюю производительность, если точки поворота выбираются случайным образом (в идеале вы должны выбрать медианное значение, но это может быть дорогостоящим). Однако за это приходится платить: ваш поиск больше не является детерминированным.

С помощью StartClient 3.x необходимо выполнить следующее:

Protocol easyHttps = new Protocol("https", new EasySSLProtocolSocketFactory(), 443);
Protocol.registerProtocol("https", easyHttps);

Реализацию EasySSLProtocolSocketFactory можно найти здесь .

Вот что я нашел:

Делать это с регулярными выражениями - кошмар. Вы можете сделать большую часть этого с помощью нескольких простых выражений, но тогда краевые случаи являются убийством. Я оказался в ужасном, хрупком беспорядке, который едва работает с одной кодовой базой.

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

Я закончил с довольно уродливым дизайном (синтаксический анализатор и трансформатор в одном - в основном, просто изменение или переиздание токенов), потому что казалось слишком много работы по созданию полезного синтаксического дерева с поддерживаемым пробелом (я хотел, чтобы результирующий код был читаемым человеком).

Я хотел попробовать phc для этого, но не смог убедить его настроить , что я создал требуемую версию библиотеки Boost.

Я еще не пробовал ANTLR для этого, но это, вероятно, лучший инструмент для такого рода задач.

Быстрый запуск в O (n log n) ожидаемое/среднее время, но O (n ^ 2) наихудший случай. Это происходит, если выбранная опора является либо минимальной, либо максимальной.

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

Последний метод делает быструю сортировку недетерминированной из-за случайности, присущей процессу сводного выбора.

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

Это связано с разделением (или шагом разделения из знаменитого "Разделяй и властвуй", который используется в Quick sort). Если каждый раз в качестве стержня для разбиения используется последний (или первый элемент, или элемент в любой позиции, только это должна быть одна и та же позиция при каждом разбиении набора данных), то это детерминированная быстрая сортировка. Если стержень выбирается случайным образом, то это рандомизированная быстрая сортировка.

Вот конспект лекций, в котором это изложено.

Надеюсь, это поможет

будьте здоровы

Распространенные прилагательные перед быстрой сортировкой являются детерминированными и рандомизированными. Детерминированный означает, что быстрая сортировка всегда будет сортировать один и тот же набор данных одним и тем же способом, в то время как рандомизированная быстрая сортировка использует рандомизацию и редко будет сортировать одни и те же данные одинаково точно (если набор данных не очень маленький - тогда это чаще) .

Детерминированный

Все сводится к выбору точек поворота. В детерминированной быстрой сортировке опорные точки выбираются либо всегда, выбирая опорную точку с одним и тем же относительным индексом, таким как первый, последний или средний элемент, либо используя медианное значение любого количества заранее заданных вариантов выбора элементов. Например, распространенным методом является выбор медианы первого, последнего и среднего элементов в качестве точки поворота. Даже с использованием только что описанного метода медианы из 3 некоторые наборы данных могут легко дать временную сложность O (N ^ 2). Примером набора данных является так называемый набор данных «органные трубы»:

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]

Рандомизированные

Рандомизированные быстрые сортировки могут выбирать только случайную опорную точку или использовать медиану некоторого количества случайно выбранных опорных точек.По-прежнему существует вероятность временной сложности O (N ^ 2), но вероятность намного, намного меньше и становится меньше с увеличением размера набора данных.

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

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