Quicksort: Выбор центра

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

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

, Например, распределение органа (1,2,3... N/2.. 3,2,1), в общем и целом и будет 1 и случайный индекс, будет некоторое число, больше, чем 1, брать медиану дает 1 (или сначала или в последний раз), и Вы получаете чрезвычайно несбалансированное разделение.

Никогда не выбирайте фиксированный центр - это может подвергнуться нападению для использования худшего случая алгоритма O (n^2) время выполнения, которое просто напрашивается на неприятности. Худшее время выполнения случая Quicksort происходит при разделении результатов в одном массиве 1 элемента и одном массиве n-1 элементов. Предположим, что Вы выбираете первый элемент в качестве своего раздела. Если кто-то подаст массив к Вашему алгоритму, который является в порядке убывания, Ваш первый центр будет самым большим, таким образом, все остальное в массиве переместится налево от него. Тогда, когда Вы рекурсивно вызываете, первый элемент будет самым большим снова, так еще раз Вы помещаете все налево от него и так далее.

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

, Если Вы абсолютно хотите гарантировать O (nlgn) время выполнения для алгоритма, columns-5 метод для нахождения медианы массива выполняет в O (n) время, что означает, что уравнение повторения для quicksort в худшем случае будет T (n) = O (n) (найдите медиану), + O (n) (раздел) + 2T (n/2) (рекурсивно вызывают левый и правый.) Основной Теоремой это - O (n LG n). Однако постоянный множитель будет огромен, и если худшая производительность случая является Вашей первоочередной задачей, используйте сортировку слиянием вместо этого, которая только немного медленнее, чем quicksort в среднем и гарантирует O (nlgn) время (и будет намного быстрее, чем эта хромая медиана quicksort).

Объяснение Медианы Алгоритма Медиан

Heh, я просто преподавал этот класс.

существует несколько опций.
Простой: Выберите первый или последний элемент диапазона. (плохо на частично отсортированном входе) Лучше: Выберите объект посреди диапазона. (лучше на частично отсортированном входе)

Однако выбор любого произвольного элемента рискует плохо делить массив размера n в два массива размера 1 и n-1. Если Вы делаете это достаточно часто, Ваш quicksort рискует становиться O (n^2).

Одно улучшение, которое я видел, является медианой выбора (сначала, в последний раз, середина); В худшем случае это может все еще перейти к O (n^2), но вероятностно, это - редкий случай.

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

при тихом столкновении с проблемами, затем пойдите средним путем.

Это зависит от Ваших требований. Выбор центра наугад делает его тяжелее для создания набора данных, который генерирует O (N^2) производительность. 'Median-three' (сначала, в последний раз, середина) является также способом избежать проблем. Остерегайтесь относительной производительности сравнений, хотя; если Ваши сравнения являются дорогостоящими, то Mo3 делает больше сравнений, чем выбор (единственное значение центра) наугад. Записи базы данных могут быть дорогостоящими для сравнения.

Обновление: Получение по запросу комментариев в ответ.

mdkess утверждал:

'Медиана 3' НЕ является сначала прошлой серединой. Выберите три случайных индекса и примите среднее значение этого. Самое главное должно удостовериться, что Ваш выбор центров не детерминирован - если это, худшие данные случая могут быть довольно легко сгенерированы.

, На который я ответил:

• Анализ Алгоритма Находки Hoare С Разделом Median-Three (1997) P Kirschenhofer, H Prodinger, C MartГ-nez поддерживает Вашу конкуренцию (что 'median-three' является тремя случайными объектами).

• существует статья, описанная в portal.acm.org , который является о 'Худшей Перестановке Случая для Median-Three Quicksort' Hannu ErkiГ ¶, опубликован в Компьютерном Журнале, Vol 27, № 3, 1984. [Обновление 26.02.2012: Получил текст для статья . Разделите 2 'Алгоритм', начинается: ' При помощи медианы первых, средних и последних элементов [L:R], эффективные разделы в части довольно равных размеров могут быть достигнуты в большинстве практических ситуаций. ' Таким образом, это обсуждает первую середину последний подход Mo3.]

• Другая короткая статья, которая интересна, доктором медицины McIlroy, "Уничтожающий Противник для Quicksort" , опубликована в Практике программного обеспечения и Опыте, Издании 29 (0), 1†“4 (0 1999). Это объясняет, как заставить почти любой Quicksort вести себя квадратично.

• AT& T Технический Журнал Bell Labs, октябрь 1984 "Теория и Практика в Конструкции Рабочей Программы сортировки" состояния "Hoare предложил делить вокруг медианы нескольких случайным образом выбранных строк. Sedgewick [...] рекомендовал выбрать медиану первого [...] в последний раз [...] и середина". Это указывает, что оба метода для 'median-three' известны в литературе. (Обновление 23.11.2014: статья, кажется, доступна в IEEE Xplore или от Wiley —, если Вы имеете членство или готовы внести плату.)

• 'Разработка Функция Вида' J L Бентли и M D McIlroy, опубликованный в Практике программного обеспечения и Опыте, Vol 23 (11), ноябрь 1993, входит в обширное обсуждение проблем, и они выбрали адаптивный алгоритм разделения, базирующийся частично на размере набора данных. Существует большое обсуждение компромиссов для различных подходов.

• поиск Google А 'median-three' работает вполне прилично на дальнейшее отслеживание.

спасибо за информацию; я только встретился с детерминированным 'median-three' прежде.

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

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

Однако для связанного списка, выбирая что-либо помимо первого, просто усугубит положение. Это выбирает средний объект в перечисленном списке, необходимо было бы ступить через него на каждый шаг раздела - добавление O (N/2) операция, которая сделана logN времена, делая общее время O (1,5 Н *регистрируют N), и это - то, если мы знаем, какой длины список - прежде чем мы запустим - обычно мы не делаем так, мы должны были бы ступить полностью до, считают их, затем ступают на полпути до находки середина, затем ступают в течение третьего раза, чтобы сделать фактический раздел: O (2.5 Н * регистрируют N)