76
правок
Изменения
→Пример: Пояснил за нахождение ключей
|-
|<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>
|}
|-
|<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>B</tex> в начале пуста, то <tex>\mathtt{merged}=C_1^s</tex>. Тогда, присвоив Присвоим ключи элементов в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, получим:действуя обратной перестановкой смещений <tex>\xi_1</tex> на последовательность ключей в отсортированном блоке.
{|11
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Первый блокСортированный
|-
| <tex>\pi</tex> ||<tex>93</tex>||<tex>34</tex>||<tex>108</tex>||<tex>49</tex>||<tex>810</tex>
|-
| <tex>key</tex> ||<tex>41</tex>||<tex>12</tex>||<tex>53</tex>||<tex>24</tex>||<tex>35</tex>
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|СортированныйПервый блок|-| <tex>\pi</tex> ||<tex>9</tex>||<tex>3</tex>||<tex>10</tex>||<tex>4</tex>||<tex>8</tex>
|-
| <tex>\pikey</tex> ||<tex>34</tex>||<tex>41</tex>||<tex>85</tex>||<tex>92</tex>||<tex>103</tex>
|-
| <tex>key\xi_1</tex> ||<tex>14</tex>||<tex>21</tex>||<tex>35</tex>||<tex>42</tex>||<tex>53</tex>
|}
|}
|}
|}
Получаем ключи элементов в <tex>C_2^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_2</tex>:
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Второй блокCортированный
|-
| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>125</tex>||<tex>6</tex>||<tex>512</tex>
|-
| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>85</tex>||<tex>6</tex>||<tex>58</tex>
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|CортированныйВторой блок|-| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>12</tex>||<tex>6</tex>||<tex>5</tex>
|-
| <tex>\pikey</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>58</tex>||<tex>6</tex>||<tex>125</tex>
|-
| <tex>key\xi_2</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>64</tex>||<tex>83</tex>
|}
|}
|}
|}
Получаем ключи элементов в <tex>C_3^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_3</tex>:
{|
|-
| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>
|-
| <tex>\xi_3</tex> ||<tex>1</tex>||<tex>2</tex>
|}
|}
