Что такое детерминированная быстрая сортировка?

Question

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

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

Answer 1

Обычная («детерминированная») быстрая сортировка может иметь очень плохое поведение в определенных наборах данных (например, реализация, которая выбирает первый несортированный элемент, имеет O (n ^ 2) временную сложность для уже отсортированных данных). *

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

Answer 2

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

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

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

Answer 3

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

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

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

Answer 4

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

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

Все сводится к выбору опорных точек. В детерминированной быстрой сортировке стержни выбираются либо всегда выбирая стержень с тем же относительным индексом, как первый, последний или средний элемент, либо используя медиану любого числа предопределенных элементов выбора. Например, распространенным методом является выбор медианы первого, последнего и среднего элементов в качестве оси. Даже с помощью метода медианы-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) временной сложности, но вероятность намного, намного меньше и становится меньше с увеличением размера набора данных.

Answer 5

Это связано с разделением (или шагом деления от знаменитого Divide and Conquer, который используется в быстрой сортировке). Если каждый раз, когда последний (или первый элемент или элемент в любой позиции, просто то, что он должен быть одной и той же позиции каждый раз, когда набор данных разделяется), используется как основание для разделения, то это - Детерминированная Быстрая сортировка. Если пивот выбран случайным образом, то это быстрая рандомизированная сортировка.

Вот примечание к лекции , в котором оно помещено.

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

ура

Answer 6

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

Answer 7

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

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