Изменения

Перейти к: навигация, поиск

Сортировка Хана

64 байта добавлено, 00:14, 8 июня 2015
Нет описания правки
==Сортировка по ключу==
Предположим, что <tex dpi="130">n</tex> чисел должны быть отсортированы, и в каждом <tex dpi="130">\log m</tex> бит. Будем считать, что в каждом числе есть <tex dpi="130">h</tex> сегментов, в каждом из которых <tex dpi="130">\log </tex> <tex dpi="150">\frac{m/}{h}</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex dpi="130">2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex dpi="130">n</tex> чисел по <tex dpi="130">\log m</tex> бит в каждом стала задачей по сортировке <tex dpi="130">n</tex> чисел по <tex dpi="130">\log </tex> <tex dpi="150">\frac{m/}{h}</tex> бит в каждом.
Операция '''сортировки за линейное время''' (англ. ''Linear-Time-Sort'')
Входные данные: <tex dpi="150">r > = \geqslant n^{\frac{2}{5}}</tex> чисел <tex dpi="130">d_{i}</tex>, <tex dpi="130">d_{i}.value</tex> — значение числа <tex dpi="130">d_{i}</tex>, в котором <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, <tex dpi="130">d_{i}.set</tex> — набор, в котором находится <tex dpi="130">d_{i}</tex>. Следует отметить, что всего есть <tex dpi="130">t</tex> наборов.
# Сортируем все <tex dpi="130">d_{i}</tex> по <tex dpi="130">d_{i}.value</tex>, используя bucket sort. Пусть все отсортированные числа в <tex dpi="130">A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex dpi="150">n^{\frac{2}{5}}</tex> чисел.
25
правок

Навигация