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) |
Сайт сортировки (веб-архив)
Патент на алгоритм (pdf)