Использование красных черных деревьев для сортировки

Question

Время выполнения вставки в red-black tree в худшем случае равно O(lg n), и если я выполняю in-order walk в дереве, я, по сути, посещаю каждый узел, поэтому общее время выполнения в худшем случае для печати отсортированной коллекциибыло бы O (n lg n)

Мне любопытно, почему red-black trees не предпочтительнее для сортировки по quick sort (среднее время выполнения которого равно O(n lg n).

Iвидите, может быть, потому что red-black trees не сортирует на месте, но я не уверен, так что, возможно, кто-то может помочь.

Answer 1

Знание того, какой алгоритм сортировки работает лучше, зависит от ваших данных и ситуации.

Если вы говорите в общих / практических терминах,

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

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

• Доступ к быстрой сортировке локализован. Это хорошо сочетается с кэшированием / обменом.

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

• Если вы попытаетесь оптимизировать сортировку двоичного дерева (используя двоичное дерево без балансировки), используя вместо этого массив, вы в конечном итоге сделаете что-то вроде быстрой сортировки!

• Красно-черные деревья имеют накладные расходы памяти. Вы должны распределять узлы возможно несколько раз, ваши требования к памяти с деревьями в два / три раза больше, чем при использовании массивов.

• После сортировки, скажем, вам нужен 1045-й (скажем) элемент, вам нужно будет вести статистику заказов в вашем дереве (из-за этого потребуется дополнительная память), и у вас будет время доступа O (logn)!

• Красно-черные деревья имеют накладные расходы только для доступа к следующему элементу (поиск по указателю)

• Красно-чёрные деревья плохо работают с кешем, и доступ к указателю может привести к большему обмену.

• Вращение в красно-черных деревьях увеличит постоянный коэффициент в O (nlogn).

• Пожалуй, самая важная причина (но не действительная, если у вас есть lib и т. Д.), Quicksort очень прост для понимания и реализации. Даже школьник может это понять!

Я бы сказал, что вы пытаетесь измерить обе реализации и посмотреть, что произойдет!

Кроме того, Боб Седжвик сделал диссертацию по быстрой сортировке! Может стоит прочитать.

Answer 2

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

Часто встроенные сортировки используют комбинацию различных методов в зависимости от значений n.

Answer 3

Во многих случаях красные деревья неплохо подходят для сортировки. Мое тестирование показало, что по сравнению с естественной сортировкой слиянием красно-черные деревья превосходят где:

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

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

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

Суть с тестами здесь .

П.С .: Следует отметить, что использование деревьев для сортировки нетривиально. Нужно не только предоставить подпрограмму вставки, но также подпрограмму, которая может линеаризовать дерево обратно в массив. В настоящее время мы используем get_last и подпрограмму предшественника, которой не требуется стек. Но эти процедуры не являются O (1), так как они содержат циклы.

Answer 4

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

«Думаю, вы работаете на очень медленном компьютере».

1. Первым делом одна операция сравнения занимает 1 час.
2. Одна операция смены занимает 2 часа.

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

Теперь из всех операций сортировки быстрая сортировка имеет очень очень мало сравнений и очень мало мест для замены элементов.

Быстрая сортировка выполняется быстрее по этой основной причине.

Answer 5

Обычно представления алгоритмов O (nlgn) могут быть расширены до A * nlgn + B, где A и B - константы. Есть много алгоритмических доказательств, которые показывают, что коэффициенты для быстрой сортировки меньше, чем у других алгоритмов. Это в лучшем случае (быстрая сортировка ужасно работает с отсортированными данными).

Answer 6

Меры сложности времени Big-O обычно не учитывают скалярные коэффициенты, например, O (2n) и O (4n) обычно просто сводятся к O (n).Анализ временной сложности основан на этапах работы на алгоритмическом уровне, а не на уровне строгого программирования, т. Е. Без учета исходного кода или собственных машинных инструкций.

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

В результате красныйчерные деревья имеют более высокие скалярные коэффициенты, чем быстрые сортировки, которые скрываются стандартным O (n log n) результатом анализа средней сложности за время.

Некоторые другие практические соображения, касающиеся архитектуры машин, кратко обсуждаются в Статья о быстрой сортировке в Википедии