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

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

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

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

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

Ответ 4

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

Ответ 5

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

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

Я надеюсь, что это поможет

веселит

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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