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

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

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

  • Пузырьковая сортировка — 2 прямых итератора прекрасно подойдут, один перетаскивая за другим.
  • Сортировка вставками — подойдут 2 двунаправленных итератора. Один для неупорядоченного элемента, один для точки вставки.
  • Сортировка выбором. Немного сложнее, но прямые итераторы могут помочь.

Быстрая сортировка

Introsort_loop в std::sort (как в стандартной библиотеке gnu/hp(1994)/silicon Graphics(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. Я еще не пробовал фактическую реализацию.


c++ algorithm quicksort stl-algorithm
person Captain Giraffe    schedule 28.09.2011    source источник
comment
Для сортировки вставками достаточно прямых итераторов. Вы можете использовать комбинацию std::rotate и std::upper_bound для реализации вставок, и оба ингредиента требуют только прямых итераторов. Конечно, это все еще O (N ^ 2).   -  person TemplateRex    schedule 13.07.2012

Ответы (3)


arrow_upward
1
arrow_downward

tl;dr: Да

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

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

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

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

person bitmask    schedule 28.09.2011
comment
Оптимизация (время выполнения) очень важна в этом контексте. Я не обращал внимания на тот факт, что связанный список может быть отсортирован в N log N. Ваше предложение увеличить на полшага медианную ось разумно, но у меня сложилось впечатление, что оно создает такое же количество накладных расходов, как и мое предложение для разделения. - person Captain Giraffe; 28.09.2011
comment
Это общеизвестно? Во всем, что я прочитал, а это довольно много, я не встретил ни одного примера выполнения сортировки N log N в связанном списке. Теперь, когда мне нужно было проверить :-) list::sort, конечно же, NlogN. - person Captain Giraffe; 28.09.2011
comment
Что ж, Omega(n log n) — это нижняя граница для сортировки на основе сравнения, и ее можно достичь. Единственное, чего нет в списке, — это произвольный доступ. Итак, если вы можете имитировать произвольный доступ (как я предложил), я не вижу причин, по которым вы должны подчеркивать связанный список при обсуждении скорости сортировки. К вашему наводящему подозрению: оцените, если это действительно имеет значение - по-другому не скажешь. - person bitmask; 29.09.2011

arrow_upward
2
arrow_downward

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

person fredoverflow    schedule 28.09.2011
comment
Итак, если мы используем рекурсивную защиту глубины, двунаправленная сортировка может выполняться за O(N log N)? (отредактировано :) - person Captain Giraffe; 28.09.2011
comment
На самом деле вы можете легко выбрать опорную точку из середины последовательности за $O(n)$ с помощью двунаправленных итераторов, не влияя на общую временную сложность. - person avakar; 28.09.2011
comment
@Captain Giraffe: вы все еще можете выбрать опорный элемент из середины - тогда это O (n), чтобы выбрать опорную точку вместо O (1), чтобы выбрать середину массива, но это не влияет на общую сложность, поскольку в любом случае вы делаете шаг O (n) для каждого поворота: раздел. Просто дополнительный обход может умножить общее время примерно на 1,5, чтобы взять середину или взять случайно выбранную опорную точку. Или, что еще хуже, если вы хотите взять медиану из 9 точек, расположенных на одинаковом расстоянии друг от друга, или какое-то другое захватывающее правило выбора опорной точки. - person Steve Jessop; 28.09.2011
comment
@Steve Да, теперь я это вижу :-) авакар, тоже верно. - person Captain Giraffe; 28.09.2011
comment
Итак, почему существует list.sort() вместо std::sort(bidirectional_iterator begin, end)? - person Captain Giraffe; 28.09.2011
comment
@CaptainGiraffe, потому что list может менять местами элементы, меняя местами целые узлы, а не значения в них (что и должен делать std::sort). - person avakar; 28.09.2011

arrow_upward
1
arrow_downward

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

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

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

person AnT    schedule 28.09.2011
comment
Аргумент указателя очень важен для многих языков эталонного стиля, в том числе и здесь. Однако односвязный список должен быть довольно сложным для реализации. Единичные служебные данные должны быть как минимум такими же большими, как случайные и двунаправленные служебные данные? - person Captain Giraffe; 28.09.2011
comment
В каких случаях в этих условиях быстрая сортировка будет лучше, чем сортировка слиянием? Если только пространство не является огромным ограничивающим фактором. - person Captain Giraffe; 28.09.2011