ABC-сортировка :: ABCsort

Лексографическая поразрядная MSD-сортировка предложенная Алленом Бичиком. Предназначена для сортировки строк.

Алгоритм

Используется два вспомогательных массива.

Трекер слов — с помощью него группируются слова, имеющие одинаковые буквы в том или ином разряде. Для самого первого найденного такого слова в списке заносится значение 0. Для каждого последующего найденного слова с той же буквой в i-м разряде в трекере слов отмечается индекс предыдущего слова, соответствующего этому же признаку.

Трекер букв — в нём отмечаются индексы самого первого (или последнего) слова в списке, в котором в соответствующем разряде находится определённый символ. Отталкиваясь от этого слова, с помощью трекера слов восстанавливается цепочка всех остальных лексем, имеющих в i-м разряде соответствующую букву.

С помощью трекеров создаются и прослеживаются цепочки слов имеющие одинаковые буквы в нескольких старших разрядах. Рекурсивно продвигаясь от старших разрядов к младшим, в итоге весьма быстро формируются новые последовательности, упорядоченные в алфавитном порядке. Отсортировав слова на «A», затем сортируется «B», затем «C» и далее по алфавиту.

Патент

Алгоритм является запатентованным в США и автор метода, Аллен Бичик, требует за коммерческое использование сортировки материальное вознаграждение. Полная лицензия стоит 88 долларов.

Характеристики алгоритма

Название ABC-сортировка (ABCsort,
Allen Beechick Character sort);
Сортировка Бичика (Beechick sort)
Автор Аллен Бичик (Allen Beechick)
Лицензия Royalty Free
Год 1993
Класс Сортировки распределением
Подкласс Поразрядные сортировки
Устойчивость Да
Сравнения Нет
Сложность по времени Худшая O(n × k)
Средняя O(n × k)
Лучшая O(n)
Сложность по памяти Дополнительная O(n)

Ссылки

Хабрахабр: ABC-сортировка

Сайт сортировки
Реализация Лина Д. Ярбро на C++
Патент на алгоритм (pdf)
Аппаратная реализация в интегральных миксросхемах (pdf)

Добавить комментарий