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>\xi_i</tex>. ====Пример====Предположим, назовем ее что <tex>m=5</tex>. Исходно получаем: {| class="wikitable" style="text-align:center"| Блок ||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#CFCFFF"|<tex>3</tex>||style="background:#CFCFFF"|<tex>3</tex>|-|<tex>\pi</tex>||style="background:#FFC9C9"|<tex>9</tex>||style="background:#FFC9C9"|<tex>3</tex>||style="background:#FFC9C9"|<tex>10</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>8</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>12</tex>||style="background:#B9FFB9"|<tex>6</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#CFCFFF"|<tex>7</tex>||style="background:#CFCFFF"|<tex>11</tex>|-|Смещение ||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>2</tex>||style="background:#FFC9C9"|<tex>3</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>5</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>3</tex>||style="background:#B9FFB9"|<tex>4</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#CFCFFF"|<tex>1</tex>||style="background:#CFCFFF"|<tex>2</tex>|} После сортировки:{| class="wikitable" style="text-align:center"|Блок ||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#CFCFFF"|<tex>3</tex>||style="background:#CFCFFF"|<tex>3</tex>|-|<tex>\pi</tex> ||style="background:#FFC9C9"|<tex>3</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>8</tex>||style="background:#FFC9C9"|<tex>9</tex>||style="background:#FFC9C9"|<tex>10</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#B9FFB9"|<tex>6</tex>||style="background:#B9FFB9"|<tex>12</tex>||style="background:#CFCFFF"|<tex>7</tex>||style="background:#CFCFFF"|<tex>11</tex>|-|Смещение ||style="background:#FFC9C9"|<tex>2</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>5</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>3</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#B9FFB9"|<tex>4</tex>||style="background:#B9FFB9"|<tex>3</tex>||style="background:#CFCFFF"|<tex>1</tex>||style="background:#CFCFFF"|<tex>2</tex>|} Обратные перестановки (<tex>\xi</tex>.):{| class="wikitable" style="center" style="background:#FFCC80"! colspan="5"|<tex>1</tex> || colspan="5"|<tex>2</tex> || colspan="3"|<tex>3</tex>|-align="center" | style="background:#FFD0D0"|<tex>4</tex>||style="background:#FFD0D0"|<tex>1</tex>||style="background:#FFD0D0"|<tex>5</tex>||style="background:#FFD0D0"|<tex>2</tex>||style="background:#FFD0D0"|<tex>3</tex>| style="background:#D0FFD0"|<tex>1</tex>||style="background:#D0FFD0"|<tex>2</tex>||style="background:#D0FFD0"|<tex>5</tex>||style="background:#D0FFD0"|<tex>4</tex>||style="background:#D0FFD0"|<tex>3</tex> | style="background:#D0D0FF"|<tex>1</tex>||style="background:#D0D0FF"|<tex>2</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>\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>\xixi_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"
Обновляем ключи в очереди:
{| 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>
Обновление старых ключей:
{| 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>
