abc-сортировка

Всё что не связано с программированием на C++ и Lua.
Ответить
Diatlo
c7i.team
Сообщения: 251
Зарегистрирован: Пт ноя 06, 2009 6:04 am

abc-сортировка

Сообщение Diatlo » Вт ноя 12, 2013 12:50 pm

http://habrahabr.ru/post/201534/

Интересный алгоритм. Исходные строки не сортируются, сама сортировка в 2 вспомогательных числовых массивах.


В среднем в 2-3 раза быстрее чем быстрая сортировка, в зависимости от списка.
Устойчивость.
Нет вырожденных случаев.
Не использует сравнения.
Не использует обмены.
Не использует опорные элементы.
Работает одинаково хорошо с короткими и с длинными списками.
Экономична по памяти.
Первые отсортированные элементы уже доступны для использования в других процессах, пока сортируется оставшаяся часть списка (другими словами – сортировка устойчива).

Чем ещё хороша сортировка – в отличие от классической MSD-radix sort сортирует не по всем разрядам. Процесс прекращается сразу как только список будет отсортирован, а не до тех пор пока не обработаются все разряды. Так же можно указать количество первых разрядов по которым произведётся упорядочивание, если старшинство по младшим разрядам не имеет особого значения.
Т.е. если нужно отсортировать по 3 первым символам - то индексируется только 3 первых символа, все что после 3 символа остается в исходном порядке

Ответить