требования к итератору для быстрой сортировки

Question

tl; dr: Можно ли эффективно реализовать быструю сортировку в двусвязном списке? Мое понимание, прежде чем думать об этом, было, нет, его нет.

На днях у меня была возможность рассмотреть требования к итераторам для основных алгоритмов сортировки. Основные O (N²) довольно просты.

• Bubble sort - 2 итератора вперед будут работать хорошо, один перетаскивая за другим.
• Сортировка вставок - подойдут 2 двунаправленных итератора. Один для элемента, вышедшего из строя, другой для точки вставки.
• Сортировка выбора - немного хитрее, но передовые итераторы могут сделать свое дело.

Quicksort

introsort_loop в std :: sort (как в стандартной библиотеке gnu / hp (1994) / кремниевой графике (1996)) требует, чтобы он был random_access.

__introsort_loop(_RandomAccessIterator __first,
         _RandomAccessIterator __last,
         _Size __depth_limit, _Compare __comp)

Как я и ожидал.

Теперь при ближайшем рассмотрении я не могу найти реальную причину, чтобы потребовать это для быстрой сортировки. Единственное, что явно требует random_access_iterators - это вызов std::__median, который требует вычисления среднего элемента. Обычная ванильная быстрая сортировка не не вычисляет медиану.

Разделение состоит из чека

 if (!(__first < __last))
    return __first;

Не очень полезная проверка для двунаправленных сообщений. Тем не менее, можно заменить это проверкой в ​​предыдущем ходе разбиения (слева направо / справа налево) с простым условием

if ( __first == __last ) this_partitioning_is_done = true;

Возможно ли реализовать быструю сортировку достаточно эффективно, используя только двунаправленные итераторы? Рекурсивная глубина все еще может быть защищена.

NB. Я еще не пытался фактической реализации.

Answer 1

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

Answer 2

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

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

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

Answer 3

тл; др: Да

Как вы говорите, проблема состоит в том, чтобы найти элемент pivot, который является элементом в середине, поиск с произвольным доступом занимает O (1), а поиск с помощью двунаправленных итераторов - O (n) (n / 2 операций , точнее). Тем не менее, на каждом шаге вы должны создавать суб-контейнеры, левый и правый, содержащие меньшие и большие числа соответственно. Именно здесь происходит основная работа по быстрой сортировке, верно?

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

Вам нужно только найти первый стержень, который на самом деле не имеет значения, потому что O (n log n + n / 2) = O (n log n).

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