Быстрая сортировка по нескольким ключам

Быстрая сортировка с несколькими ключами , также известная как трехходовая радикальная быстрая сортировка , ^[1] — это алгоритм сортировки строк . Этот гибрид быстрой сортировки и радиальной сортировки был первоначально предложен П. Шеклтоном, как сообщалось в одной из основополагающих статей К. А. Р. Хоара по быстрой сортировке ; [ ^2]^{: 14} его современное воплощение было разработано Джоном Бентли и Робертом Седжвиком в середине 1990-х годов. ^[3] Алгоритм разработан для использования того свойства, что во многих задачах строки, как правило, имеют общие префиксы .

Одним из применений алгоритма является построение массивов суффиксов , для чего он был одним из самых быстрых алгоритмов по состоянию на 2004 год. ^[4]

Описание

Трехходовой алгоритм быстрой сортировки по основанию сортирует массив из $N$ ( указателей на) строк в лексикографическом порядке . Предполагается, что все строки имеют одинаковую длину $K$ ; если строки имеют разную длину, они должны быть дополнены дополнительными элементами, которые меньше любого элемента в строках. ^[a] Псевдокод для алгоритма тогда будет ^[b]

алгоритм sort(a : массив строк, d : целое число) —  если длина(a) ≤ 1 или d ≥ K, то  возвращается p := pivot(a, d) i, j := partition(a, d, p) (Обратите внимание на одновременное назначение двух переменных.) сортировка(a[0:i), d) сортировка(a[i:j), d + 1) сортировать(a[j:длина(a)), d)

В отличие от большинства алгоритмов сортировки строк, которые просматривают множество байтов в строке, чтобы решить, является ли строка меньше, такой же или равной некоторой другой строке; а затем переключают свое внимание на некоторую другую пару строк, быстрая сортировка с несколькими ключами изначально просматривает только один байт каждой строки в массиве, byte d, изначально первый байт каждой строки. Рекурсивный вызов использует новое значение dи передает подмассив, где каждая строка в подмассиве имеет точно такую же начальную часть — символы перед character d.

Функция pivot должна возвращать один символ. Бентли и Седжвик предлагают либо выбрать медиану a [0][d], ..., a[length(a)−1][d], либо какой-либо случайный символ в этом диапазоне. ^[3] Функция разбиения является вариантом той, которая используется в обычной трехсторонней быстрой сортировке : она перестраивает a так, что все a[0], ..., a[i−1] имеют элемент в позиции d, который меньше p , a[i], ..., a[j−1] имеют $p$ в позиции $d$ , а строки от $j$ и далее имеют d -й элемент больше $p$ . (Исходная функция разбиения, предложенная Бентли и Седжвиком, может быть медленной в случае повторяющихся элементов; для облегчения этого можно использовать разбиение с голландским национальным флагом . ^[5] )

Практическая реализация быстрой сортировки с несколькими ключами может выиграть от тех же оптимизаций, которые обычно применяются к быстрой сортировке: выбор медианы из трех, переключение на сортировку вставкой для небольших массивов и т. д. ^[6]

Смотрите также

Сортировка «Американский флаг» — еще один вариант радиальной сортировки, который быстро сортирует строки.
Троичное дерево поиска – трехсторонняя радикальная быстрая сортировка изоморфна этой структуре данных таким же образом, как быстрая сортировка изоморфна бинарным деревьям поиска ^[3]

Примечания

^ Один из способов сделать это, не изменяя представление строк в памяти, — индексировать их с помощью функции, которая возвращает −1 или какое-либо другое небольшое значение, если индекс выходит за пределы диапазона.
^ Массивы и строки индексируются нулем. Срез массива a[i:j) выдает подмассив a от i до j (исключая) и предполагается, что это некопирующая операция с постоянным временем.

Ссылки

^ В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "multikey Quicksort". Словарь алгоритмов и структур данных . NIST .
^ Хоар, АВТОМОБИЛЬ (1962). «Быстрая сортировка». Вычислить. Дж. 5 (1): 10–16 . doi : 10.1093/comjnl/5.1.10 .
^ abc Бентли, Джон; Седжвик, Роберт (1997). Быстрые алгоритмы сортировки и поиска строк (PDF) . Proc. Ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA). ISBN 0-89871-390-0.
^ Манзини, Джованни; Феррагина, Паоло (2004). «Разработка алгоритма построения облегченного массива суффиксов». Algorithmica . 40 : 33–50 . CiteSeerX 10.1.1.385.5959 . doi :10.1007/s00453-004-1094-1.
^ Ким, Ынсан; Пак, Кунсу (2009). «Улучшение быстрой сортировки по нескольким ключам для сортировки строк с большим количеством одинаковых элементов». Information Processing Letters . 109 (9): 454– 459. doi :10.1016/j.ipl.2009.01.007.
^ Бентли, Джон; Седжвик, Роберт (1998). «Сортировка строк с помощью быстрой сортировки по трем основаниям». Журнал доктора Добба .

[5] Один из способов сделать это, не изменяя представление строк в памяти, — индексировать их с помощью функции, которая возвращает −1 или какое-либо другое небольшое значение, если индекс выходит за пределы диапазона.

[6] Массивы и строки индексируются нулем. Срез массива a[i:j) выдает подмассив a от i до j (исключая) и предполагается, что это некопирующая операция с постоянным временем.

[1] В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "multikey Quicksort". Словарь алгоритмов и структур данных . NIST .

[2] Хоар, АВТОМОБИЛЬ (1962). «Быстрая сортировка». Вычислить. Дж. 5 (1): 10–16 . doi : 10.1093/comjnl/5.1.10 .

[soda-3] Бентли, Джон; Седжвик, Роберт (1997). Быстрые алгоритмы сортировки и поиска строк (PDF) . Proc. Ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA). ISBN 0-89871-390-0.

[4] Манзини, Джованни; Феррагина, Паоло (2004). «Разработка алгоритма построения облегченного массива суффиксов». Algorithmica . 40 : 33–50 . CiteSeerX 10.1.1.385.5959 . doi :10.1007/s00453-004-1094-1.

[7] Ким, Ынсан; Пак, Кунсу (2009). «Улучшение быстрой сортировки по нескольким ключам для сортировки строк с большим количеством одинаковых элементов». Information Processing Letters . 109 (9): 454– 459. doi :10.1016/j.ipl.2009.01.007.

[8] Бентли, Джон; Седжвик, Роберт (1998). «Сортировка строк с помощью быстрой сортировки по трем основаниям». Журнал доктора Добба .