47
правок
Изменения
→Деление на блоки: Исправлена логическая ошибка
Получим сортированные варианты этих блоков <tex>C_j^S</tex>. При лобовой {{Acronym|цифровой|radix}} сортировке мы получим <tex>O(\frac{n}{m}n)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, {{Acronym|рассматривая номер блока как старший разряд, элемент как младший разряд|по смещению внутри блока не сортируем}}, можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>.
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>
==== Пример ====
Пусть <tex>m = 5</tex>. Исходно:
|Смещение ||style="background:#FF8080"|2||style="background:#FF8080"|4||style="background:#FF8080"|5||style="background:#FF8080"|1||style="background:#FF8080"|3||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|4||style="background:#80FF80"|3||style="background:#8080FF"|1||style="background:#8080FF"|2
|}
Обратные перестановки (<tex>\xi</tex>):
{| class="wikitable" style="center" style="background:#FFCC80"
! colspan="5"|1 || colspan="5"|2 || colspan="3"|3
|-align="center"
| style="background:#FFD0D0"|4||style="background:#FFD0D0"|1||style="background:#FFD0D0"|5||style="background:#FFD0D0"|2||style="background:#FFD0D0"|3
| style="background:#D0FFD0"|1||style="background:#D0FFD0"|2||style="background:#D0FFD0"|5||style="background:#D0FFD0"|4||style="background:#D0FFD0"|3
| style="background:#D0D0FF"|1||style="background:#D0D0FF"|2
|}
=== Обработка блока ===
==== Основная идея ====
