Быстрая сортировка с несколькими ключами
Быстрая сортировка с несколькими ключами , также известная как быстрая поразрядная сортировка с тремя путями . [1] это алгоритм сортировки строк — . Этот гибрид быстрой сортировки и поразрядной сортировки был первоначально предложен П. Шеклтоном, как сообщается в одной из К. А. Хоара основополагающих статей о быстрой сортировке ; [2] : 14 его современное воплощение было разработано Джоном Бентли и Робертом Седжвиком в середине 1990-х годов. [3] Алгоритм разработан с учетом того свойства, что во многих задачах строки имеют общие префиксы .
Одним из применений алгоритма является построение суффиксных массивов , для чего по состоянию на 2004 год это был один из самых быстрых алгоритмов. [4]
Описание
[ редактировать ]Алгоритм трехсторонней быстрой сортировки по основанию сортирует массив из N строк ( указателей на) в лексикографическом порядке . Предполагается, что все строки имеют одинаковую длину K ; если строки имеют разную длину, они должны быть дополнены дополнительными элементами, размер которых меньше любого элемента в строках. [а] Тогда псевдокод алгоритма будет [б]
algorithm sort(a : array of string, d : integer) is
if length(a) ≤ 1 or d ≥ K then
return
p := pivot(a, d)
i, j := partition(a, d, p) (Note a simultaneous assignment of two variables.)
sort(a[0:i), d)
sort(a[i:j), d + 1)
sort(a[j:length(a)), d)
В отличие от большинства алгоритмов сортировки строк, которые просматривают множество байтов в строке, чтобы решить, является ли строка меньше, такой же или равной какой-либо другой строке; а затем переключив внимание на какую-либо другую пару строк, быстрая сортировка с несколькими ключами сначала рассматривает только один байт каждой строки в массиве, байт d, первоначально первый байт каждой строки.
Рекурсивный вызов использует новое значение d и передает подмассив, где каждая строка в подмассиве имеет одну и ту же начальную часть — символы перед символом d.
The функция поворота должна возвращать один символ. Бентли и Седжвик предлагают либо медиану выбрать a[0][d], ..., a[length(a)−1][d] или какой-либо случайный символ в этом диапазоне. [3] Функция разделения — это вариант той, которая используется в обычной трехсторонней быстрой сортировке : она переупорядочивает а так, что все a[0], ..., a[i−1] имеют элемент в позиции д, это меньше, чем п , a[i], ..., a[j−1] имеют p в позиции d , а строки, начиная с j, имеют a d 'й элемент больше, чем p . (Исходная функция разделения, предложенная Бентли и Седжвиком, может быть медленной в случае повторяющихся элементов; разделение под национальным флагом Нидерландов . для облегчения этого можно использовать [5] )
Практические реализации быстрой многоключевой сортировки могут выиграть от тех же оптимизаций, которые обычно применяются к быстрой сортировке: поворот по медиане из трех, переключение на сортировку вставками для небольших массивов и т. д. [6]
См. также
[ редактировать ]- Сортировка по американскому флагу — еще один вариант поразрядной сортировки, который обеспечивает быструю сортировку строк.
- Троичное дерево поиска - быстрая сортировка по трехстороннему основанию изоморфна этой структуре данных точно так же, как быстрая сортировка изоморфна двоичным деревьям поиска. [3]
Примечания
[ редактировать ]- ^ Один из способов сделать это, не изменяя представление строк в памяти, — это индексировать их с помощью функции, которая возвращает −1 или какое-либо другое небольшое значение, когда индекс выходит за пределы диапазона.
- ^ Массивы и строки имеют нулевой индекс. Срез массива a[i:j) дает подмассив а из я чтобы j (эксклюзивный) и предполагается, что это некопирующая операция с постоянным временем.
Ссылки
[ редактировать ]- ^
В этой статье использованы общедоступные материалы из Пол Э. Блэк. «многоклавишная быстрая сортировка» . Словарь алгоритмов и структур данных . НИСТ .
- ^ Хоар, ЦАР (1962). «Быстрая сортировка» . Вычислить. Дж. 5 (1): 10–16. дои : 10.1093/comjnl/5.1.10 .
- ^ Перейти обратно: а б с Бентли, Джон; Седжвик, Роберт (1997). Быстрые алгоритмы сортировки и поиска строк (PDF) . Учеб. Ежегодный симпозиум ACM-SIAM. по дискретным алгоритмам (SODA). ISBN 0-89871-390-0 .
- ^ Манзини, Джованни; Феррагина, Паоло (2004). «Разработка облегченного алгоритма построения суффиксного массива». Алгоритмика . 40 : 33–50. CiteSeerX 10.1.1.385.5959 . дои : 10.1007/s00453-004-1094-1 .
- ^ Ким, Ынсанг; Пак, Кунсу (2009). «Улучшение многоключевой быстрой сортировки для сортировки строк с множеством одинаковых элементов». Письма об обработке информации . 109 (9): 454–459. дои : 10.1016/j.ipl.2009.01.007 .
- ^ Бентли, Джон; Седжвик, Роберт (1998). «Сортировка строк с помощью трехсторонней быстрой сортировки» . Журнал доктора Добба .
