81
правка
Изменения
Нет описания правки
|id=lemma3.
|statement=
Выбор <tex>s</tex>-о ого наибольшего числа среди <tex>n</tex> чисел упакованных в <tex>n/g</tex> контейнеров может быть сделана за <tex>O(nlogg/g)</tex> время и с использованием <tex>O(n/g)</tex> места. Конкретно медиана может быть так найдена.
|proof=
Так как мы можем делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., <tex>g</tex>-о ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex> уберем хотя бы <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсию.
}}
{{Лемма
|proof=
Так как используется только <tex>(logn)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <tex>O(n/g)</tex> времени и места. Потому, что мы используем <tex>(logn)/2</tex> бит на контейнер нам понадобится <tex>\sqrt {n}</tex> шаблонов для всех контейнеров. Затем поместим <tex>g < (logn)/2</tex> контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более <tex>g - 1</tex> контейнеров которые не смогут образовать группу. Поэтому не более <tex>\sqrt{n}(g - 1)</tex> контейнеров не смогут сформировать группу. Для каждой группы мы помещаем <tex>i</tex>-е число во всех <tex>g</tex> контейнерах в один. Таким образом мы берем <tex>g</tex> <tex>g</tex>-целых векторов и получаем <tex>g</tex> <tex>g</tex>-целых векторов где <tex>i</tex>-ый вектор содержит <tex>i</tex>-ое число из входящего вектора. Эта транспозиция может быть сделана за время <tex>O(glogg)</tex>, с использованием <tex>O(g)</tex> места. Для всех групп это занимает время <tex>O((n/g)logg)</tex>, с использованием <tex>O(n/g)</tex> места.
Для контейнеров вне групп (которых <tex>\sqrt(n)(g - 1)</tex> штук) мы просто разберем и соберем заново контейнеры. На это потребуется не более <tex>O(n/g)</tex> места и времени. После всего этого мы используем bucket sorting вновь для сортировки <tex>n</tex> контейнеров. таким образом мы отсортируем все числа.
}}
Заметим, что когда <tex>g = O(logn)</tex> мы сортируем <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров за время <tex>O((n/g)log(logn))</tex>, с использованием O(n/g) места. Выгода очевидна.
{{Лемма
|id=lemma5.
|statement=
Если принять, что каждый контейнер содержит <tex>logm > logn</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(logm)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((nlog(logn))/g)</tex> с использованием <tex>O(n/g)</tex> места.
*: если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
|proof=
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>(logn)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Мы можем переместить каждую группу контейнеров для чисел.
}}
Заметим, что сортирующие алгоритмы в четвертой и пятой леммах нестабильные. Хотя на их основе можно построить стабильные алгоритмы используя известный метод добавления адресных битов к каждому входящему числу.
Если у нас длина контейнеров больше, сортировка может быть ускорена, как показано в следующей лемме.
