Изменения

Предположим, что <tex>n</tex> чисел должны быть сортированыотсортированы, и в каждом <tex>\log m</tex> бит. РассматриваетсяБудем считаем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>\log (m/h)</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>\log m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex> \log (m/h)</tex> бит в каждом.

Так же, Также рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, <tex>\ldots</tex>, <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Необходимо разделить <tex>S</tex> в <tex>p + 1</tex> наборов, таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.к. Так как используется '''signature sorting'''то перед тем, до того как делать вышеописанное разделение, необходимо поделить биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов, и взять некоторые из них. Так же делим биты для каждого числа из <tex>S</tex> и оставляем только один в каждом числе. По существу , для каждого <tex>a_{i}</tex> берутся все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. СегментыСегмент, которые берутся который берется для числа в <tex>S</tex> {{---}} это сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом преобразуется , начальная задача о разделении <tex>n</tex> чисел в по <tex>\log m</tex> бит преобразуется в несколько задач на разделение с числами в по <tex>\log (m/h)</tex> бит.

Делим числа на 2 сегмента. Для <tex>a_{1}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> {{---}} верхний 1, нижний 1; <tex>a_{3}</tex> {{---}} верхний 1, нижний 3; <tex>a_{4}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим: для 1: нижний 1 т.к. , так как он выделяется из нижнего сегмента <tex>a_{1}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.

Предположим, у есть Есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>, и хотется использовать . Используем числа в <tex>T</tex> для разделения набора <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex> что <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть <tex>h = \log n/(c \log p)</tex> для константы <tex>c > 1</tex>. (<tex>h/ \log\log n \log p</tex> )-битные числа могут быть хранены храниться в одном контейнере, так что одно слово хранит содержащим <tex>(\log n)/(c \log\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/ \log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, хешируются числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом)хешируются, чтобы получить и получается <tex>h/ \log\log n</tex> хешированных значений в одном контейнере. Чтобы получить значения сразу, при При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяются объединяем в один. Пусть <tex>a'_{i}</tex> {{---}} хеш-контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хеш-значения имеют <tex>(2 \log n)/(c \log\log n)</tex> бит. Хотя , хотя эти значения разделены на сегменты по <tex>h/ \log\log n</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex>(2 \log n)/(c \log\log n)</tex> бит. Потом рассматриваются рассматривается каждый хеш-контейнер как число , и сортируются эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки, биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex>сегментов. Таким образом, получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).

После того, как повторится вышеописанный процесс повторится <tex>g</tex> раз, получится неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> раз, в то время, как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся происходит за линейное время <tex>O(qt)</tex>.

Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, которые <tex>\log\log n/h</tex>-ые, <tex>(\log\log n/h)^2</tex>-ые, <tex>\ldots</tex> от всего числапо счету в числе. Для сегментов вида Хеш-функцию для <tex>(\log\log n/h)^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex>p</tex> чисел на <tex>(\log\log n/h)^t</tex> сегментов. Рассматривая каждый сегмент как число, получится получаем <tex>p(\log\log n/h)^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex>t < \log n</tex> , то, получится не более <tex>\log n</tex> хеш-функций.

Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упаковались упакованы в <tex>(2 \log n)/(c \log\log n)</tex> бит. Есть <tex>t</tex> наборов , в каждом из которых <tex>q + p</tex> хешированных контейнеров по <tex>(2 \log n)/(c \log\log n)</tex> бит в каждом. Эти числа контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.  Procedure '''Linear-Time-Sort''' Входные данные: <tex>r > = n^{2/5}</tex> чисел <tex>d_{i}</tex>, <tex>d_{i}.value</tex> — значение числа <tex>d_{i}</tex>, в котором <tex>(2 \log n)/(c \log\log n)</tex> бит, <tex>d_{i}.set</tex> — набор, в котором находится <tex>d_{i}</tex>. Следует отметить, что всего есть <tex>t</tex> наборов. # Сортируем все <tex>d_{i}</tex> по <tex>d_{i}.value</tex>, используя bucket sort. Пусть все отртированные числа в <tex>A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex>n^{2/5}</tex> чисел.# Помещаем все <tex>A[j]</tex> в <tex>A[j].set</tex>.