76
правок
Изменения
→Деление на блоки
[[Цифровая сортировка]] каждого блока отдельно будет давать нам время работы <tex>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, рассматривая номер блока как старший разряд, элемент как младший разряд (по смещению внутри блока не сортируем), можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>.
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки<tex>\xi</tex>, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденнойТ.е. если элемент <tex>\pi</tex> находится в исходной перестановке в блоке <tex>C_j</tex> на позиции <tex>i</tex>, назовем ее то в блоке <tex>C_j^s</tex> он на позиции <tex>\xixi_i</tex>.
=== Обработка блока ===Каждому элементу <tex>x</tex> взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex>. Очередь <tex>B</tex> будет работать непосредственно с ключами элементов. Определим ключи элементов так, чтобы их значения были в промежутке <tex>\{1,2,\dots,2m\}</tex>. Работая с блоком <tex>C_j</tex>, будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключи находятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>. В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливо утверждение, что <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов. После того, как мы определили новые ключи для элементов, обновляем ключи в очереди <tex>B</tex>. Затем запускаем алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порядке исходной последовательности. В итоге, обработка блока делится на следующие этапы:* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{elems}</tex>.* Сливаем элементы в <tex>\mathtt{elems}</tex> со следующим отсортированным блоком в список <tex>\mathtt{merged}</tex>.* Присваиваем новые ключи элементам в порядке списка <tex>\mathtt{merged}</tex>.* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex>.* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>. ==Пример=Пример===
Предположим, что <tex>m=5</tex>. Исходно получаем:
|}
=== Обработка блока ===
Обрабатывая блок, каждому элементу <tex>x</tex> внутри этого блока взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex> так, чтобы их значения находились в промежутке <tex>\{1,2,\dots,2m\}</tex>. Очередь <tex>B</tex> будет работать непосредственно с ключами элементов.
Работая с блоком <tex>C_j</tex>, будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключи находятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>.
В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливы утверждения, что <tex>\mathtt{elt}(x)=\mathtt{merged}[x]</tex> и <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.
Находим последовательность ключей, соответствующую элементам блока <tex>C_j^s</tex>. Действуя на эту последовательность перестановкой <tex>\xi_j</tex>, получаем последовательность ключей в порядке исходного блока.
Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
Затем запускаем алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порядке исходной последовательности.
В итоге, обработка блока делится на следующие этапы:
* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{elems}</tex>.
* Сливаем элементы в <tex>\mathtt{elems}</tex> со следующим отсортированным блоком <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>, генерируя два вспомогательных массива <tex>\mathtt{ind_0}</tex> и <tex>\mathtt{ind_1}</tex>, хранящих индексы элементов списков <tex>C_j^s</tex> и <tex>\mathtt{elems}</tex> соответственно в списке <tex>\mathtt{merged}</tex>.
* Действуя на последовательность ключей в списке <tex>\mathtt{ind_0}</tex> перестановкой <tex>\xi_j</tex> получим ключи в порядке исходной последовательности.
* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex> (элементы <tex>\mathtt{ind_1}</tex>).
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>.
====Пример====
''' Первый блок '''
Так как очередь <tex>B</tex> в начале пуста, то <tex>\mathtt{merged}=C_1^s</tex>. Присвоим ключи элементов элементам в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, действуя обратной перестановкой смещений <tex>\xi_1</tex> на последовательность ключей в отсортированном блоке.
{|11
| ||
{| class="wikitable" style="text-align:center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
|}
|}
{|
| ||
{| class="wikitable" style="center"
|-align="center"
|<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>7</tex>||<tex>8</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>\mathtt{ind_1}</tex>
|-align="center"
| <tex>3</tex>||<tex>4</tex>||<tex>7</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>\mathtt{ind_0}</tex>
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>
|}
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|CортированныйСортированный
|-
| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
Обновляем ключи в очереди:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>\pikey</tex>
|-align="center"
| style="background:#FFC9C9"| <tex>3</tex> || || || style="background: #CFCFFF"| <tex>3</tex>
| <tex>7</tex>||<tex>11</tex>
|}
|}
{|
| ||
{| class="wikitable" style="center"
|-align="center"
|<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>\mathtt{ind_1}</tex>
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>6</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>\mathtt{ind_0}</tex>
|-align="center"
| <tex>4</tex>||<tex>5</tex>
|}
|}
Обновление старых ключей:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>\pikey</tex>
|-align="center"
| style="background:#FFC9C9"| <tex>1</tex> || || || || style="background: #CFCFFF"| <tex>1</tex>
