Поразрядная сортировка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Поразрядная сортировка (англ. radix sort) — алгоритм сортировки за линейное время.

Алгоритм[править | править вики-текст]

Числа сортируются по разрядам. Существует два варианта: least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

При MSD сортировке последовательность сортируется по старшему значимому двоичному разряду так, чтобы все ключи начинающиеся с 0 оказались перед всеми ключами начинающимися с 1. Для этого необходимо найти крайний слева ключ K_i, начинающийся с 1, и крайний справа ключ K_j, начинающийся с 0. После чего K_i и K_j меняются местами, и процесс повторяется, пока не получится i > j. Пусть F_0 — множество элементов начинающихся с 0, F_1 — множество всех остальных элементов. Применим к F_0 поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F_0 полностью не рассортируется. Затем проделаем то же самое с F_1.

Применение для строк[править | править вики-текст]

Вместо сравнения N-й битовой позиции в слове сравнивается N-й байт строки.

Нулевой проход использует только нулевые символы в каждой строке и является корзинной сортировкой по нулевому символу. Эффективная реализация возможна при использовании массива ссылок на строки вместо самих строк, дополнительного массива «границ корзин», инициализируемого частотами встреч символов при первом проходе, они же число элементов в каждой «корзине». При следующем проходе заполняется массив ссылок.

N-й (для N > 0) проход выполняется последовательно над каждой корзиной, полученной на (N — 1)-м проходе, с делением её на «подкорзины». В этом проходе сравниваются N-ные символы каждой строки.

Операция завершается при N, равном максимальной длине строки, или же в ситуации, когда все «подкорзины» получили длину 1.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]