Участник:Artem.ustinov/НВП - История изменений

Artem.ustinov: /* Деление на блоки */

2018-01-19T18:42:05Z

‎Деление на блоки

94.25.229.31: /* Пример */

2018-01-19T16:58:19Z

‎Пример

Artem.ustinov: /* Обработка блока */

2018-01-17T14:58:17Z

‎Обработка блока

Artem.ustinov: /* Обработка блока */ исправил ошибки

2018-01-17T14:52:56Z

‎Обработка блока: исправил ошибки

Artem.ustinov: /* Обработка блока */

2018-01-17T14:46:05Z

‎Обработка блока

Artem.ustinov: /* Деление на блоки */

2018-01-17T14:32:49Z

‎Деление на блоки

Artem.ustinov: /* Основная идея */

2018-01-17T14:32:24Z

‎Основная идея

Artem.ustinov: /* Оптимизация до O(n log log k) */ Разделил примеры

2018-01-17T14:31:23Z

‎Оптимизация до O(n log log k): Разделил примеры

Artem.ustinov: /* Пример */ Дополнил пример

2018-01-17T14:29:15Z

‎Пример: Дополнил пример

Artem.ustinov: /* Обработка блока */ Ещё дополнил

2018-01-17T14:16:52Z

‎Обработка блока: Ещё дополнил

@@ Строка 170: / Строка 170: @@
 [[Цифровая сортировка]] каждого блока отдельно будет давать нам время работы <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>\xi</tex>, элементы которой соотносятся между собой как элементы исходного блока. Т.е. если элемент <tex>\pi</tex> находится в исходной перестановке в блоке <tex>C_j</tex> на позиции <tex>i</tex>, то в блоке <tex>C_j^s</tex> он на позиции <tex>\xi_i</tex>.
 ====Пример====

@@ Строка 344: / Строка 344: @@
 Обновляем ключи в очереди:
 {| class="wikitable" style="center" style="background: #ffffcc"
-! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>\pi</tex>
+! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>
 |-align="center"
 | style="background:#FFC9C9"| <tex>3</tex> ||   ||   || style="background: #CFCFFF"| <tex>3</tex>
@@ Строка 450: / Строка 450: @@
 Обновление старых ключей:
 {| class="wikitable" style="center" style="background: #ffffcc"
-! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>\pi</tex>
+! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>key</tex>
 |-align="center"
 | style="background:#FFC9C9"| <tex>1</tex> ||   ||   ||   || style="background: #CFCFFF"| <tex>1</tex>

@@ Строка 217: / Строка 217: @@
 * Достаем из очереди <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</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>.

@@ Строка 208: / Строка 208: @@
 В итоге, получим отсортированный список <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>C_j^s</tex>. Действуя на эту последовательность перестановкой <tex>\xi_j</tex>, получаем последовательность ключей в порядке исходного блока.
 Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
@@ Строка 225: / Строка 225: @@
 ''' Первый блок '''
-Так как очередь <tex>B</tex> в начале пуста, то <tex>\mathtt{merged}=C_1^s</tex>. Присвоим ключи элементов в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, действуя обратной перестановкой смещений <tex>\xi_1</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"

@@ Строка 208: / Строка 208: @@
 В итоге, получим отсортированный список <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>C_j^s</tex>. Действуя на эту последовательность перестановкой <tex>\xi_j</tex>, получаем последовательность ключей в порядке исходного блока.
-Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
+Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
 Затем запускаем алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порядке исходной последовательности.

← Предыдущая		Версия 14:32, 17 января 2018
Строка 171:		Строка 171:

	Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>.		Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</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>
		+	\|}

	=== Обработка блока ===		=== Обработка блока ===

← Предыдущая		Версия 14:32, 17 января 2018
Строка 161:		Строка 161:

	Во время обработки ключей элементов описанный выше алгоритм <tex>\mathrm{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, которые не находятся в очереди. Поэтому, если мы разобьем всю последовательность на блоки из <tex>m</tex> элементов (последний блок может быть меньше), и нам удастся обрабатывать каждый как перестановку из <tex>m</tex> элементов, сохраняя очередь <tex>B</tex> для вычисленных ранее блоков, то мы получим асимптотическое время <tex>O(n \operatorname{log} \operatorname{log} (k + m))</tex>, а так как <tex>m \geqslant k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока — получаем верхнее ограничение в <tex>k + m</tex> обрабатываемых возможных значений.)		Во время обработки ключей элементов описанный выше алгоритм <tex>\mathrm{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, которые не находятся в очереди. Поэтому, если мы разобьем всю последовательность на блоки из <tex>m</tex> элементов (последний блок может быть меньше), и нам удастся обрабатывать каждый как перестановку из <tex>m</tex> элементов, сохраняя очередь <tex>B</tex> для вычисленных ранее блоков, то мы получим асимптотическое время <tex>O(n \operatorname{log} \operatorname{log} (k + m))</tex>, а так как <tex>m \geqslant k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока — получаем верхнее ограничение в <tex>k + m</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>~~
−	\|}

	=== Деление на блоки===		=== Деление на блоки===

@@ Строка 290: / Строка 290: @@
 | <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
 |}
 | ||
 {| class="wikitable" style="center"
@@ Строка 298: / Строка 301: @@
 |-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>
 |}
 |}
@@ Строка 306: / Строка 323: @@
 | ||
 {| class="wikitable" style="text-align:center"
-! colspan="6"|Cортированный
+! colspan="6"|Сортированный
 |-
 | <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
@@ Строка 377: / Строка 394: @@
 | <tex>7</tex>||<tex>11</tex>
 |}
 | ||
 {| class="wikitable" style="center"
@@ Строка 385: / Строка 405: @@
 |-align="center"
 |<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>
 |}
 |}