Для Сортировки Обменом мы ограничим Перест! так, чтобы за один вызов устранялось как можно больше инверсий, а для Сортировки Взбалтыванием так, чтобы устранялась одна инверсия за вызов. Более точно, для Обмена имеем

2. Сорт!! if) Лучшая {Перест! (/))

3. Лучшая{8)(1 такая что f е S.

и Vf/eS -{f} Числоинверсий{1)

< Числоинверсий {f!)

4. Числоинверсий {f)Card {{xl \{п!х!) е f, {п2х2) а п! <п2

и х!> х2}).

Таким образом, мы имеем

5. Сорт!! {{nlxl) Ч- {п2х2) + /)

Лучшая{{{п1х!) fl \f! Перест! {(п2х2)-\- f)} и {{п!х2) + f2\f2 Перест! {{п2х!) + f)}) Лучшая {{{п!х!) + f!\fl Перест! {{п2х2) + /)})

если х! < х2 Лучшая{{{п!х2) + f2\f2 Перест! {{п2х1) + f)})

иначе

(п!х!) + Лучшая{Перест1 {{n2x2) + f)) если х! <х2 {п1х2) + Лучшая {Перест! {{п2х!) -f /)) иначе

(tt/x/) + Сорт {{п2х2) + /) если л;/ < х2 {п1х2) -f Сорт {{п2х!) + jF) иначе.

Когда Сорт!! {f) = f, ynop{f) выполняется, и можно записать

6. Сорг (/)-Ф= если u==f

то f

иначе Сорт(и)

где u = CopT!l{f).

Мы получили рекурсивную программу сортировки, но дело еще не совсем закончено. В Сортировке Обменом заключительная проверка вплетена в главную рекурсию. Здесь же она пока отделена, так как проверка и = f требует просмотра всего массива. Здесь мы только набросаем включение этой проверки в рекурсию. Предположим, что равенство между массивами и функциями вычисляется с помощью =f, главная рекурсия для которого

7. {nx)-\-f!=f{my)-\-f2

пт и у = х и f\=ff2. Тогда можно определить

8. Обмен {f)<(j=f Сорт!l{f), CopT!!{f)),

И ДЛЯ главной рекурсии имеем

9. Обмен({пх)-\-{ту)-\-!)

<=п = п и х = х и {my)-\-f=fCopTll{{my)-\-f),

{пх) + Сорт 11 {{ту) + f)) если х<у {п = п и х = у и (ту) + / =f СортП {{тх) + /), {пу) + СортП {{тх) + 1)) иначе.

Разворачивая с использованием (5), перестраивая условие и разворачивая с использованием (7)

-({Истина и {my)-\-f=fCopTll{{my)-\-f),

{пх) + СортП {{ту) + Ь) если х<у {Ложь и {ту) -\-f=f CopTl 1 {{тх) + f),

{пу) + Сорт И {{тх) + f)) иначе {Истина и м, (ttx) + у)

где {и, v) = {{my)-\-f=fCopTll{{my)-\-f),

Сорт11 {{ту) + f) если л: < г/

{Ложь, {пу) + у)

где {и, V) = {{тх) + f =f СортП {{тх) + f).

Сорт 11 {{тх-\-f)) иначе.

Обобщение. Заметим, что и не используется во втором обобщении, что позволяет нам произвести свертку

4= {и, {пх) -f v)

где {и, v) = Обмен {{ту) -f /) если х <у {Ложь {пу) -Ь v)

где {и, v) = Обмен {{mv)-\-f) иначе

Свертка с (8).

Наконец, свяжем Сорт и Обмен

10. Сорт (f)если и то f

иначе CopT{v) где {и, v) = {f=f Сорт 11(f), CopTll{f))

Обобщая (6) <?= если и то f

иначе Сорт{ь) где (м, у) = Обмен (f) Свертка с (8).

Мы не будем вдаваться в детали синтеза основных случаев, а приведем сразу алгоритм S5 {Сортировка Обменом) S5 Сорт (f)если и то f

иначе CopT{v)

где (м, у) = Обмен (f) Обмен {Ф)<= {Истина, Ф) Облек ({(ш:)}) {Истина, {{пх}})

Обмен {{пх) + {ту) + f) {и, {пх) + v)

где {и, v) = Обмен {{ту) + /)

если х<у

{Ложь, {пу)-\- v)

где {и, v) = Обмен {{тх)-\- f) иначе.

5.4.3. Сортировка Взбалтыванием из РЗ. Как уже упоминалось в предыдущем разделе, Сортировка Взбалтыванием выводится из Перест! отбором перестановок, удаляющих ровно одну инверсию (если таковая имеется).

1. Сорт2 (/) Безодного {Перест! {f), f)

2. Безодного {s, f)<= f! • такая что f/eS

и Числоинверсий {f!)-\-!= Числоинверсий {f)

если f! существует f иначе

Отсюда получаем рекурсию

3. Сорт!2 {{п!х!) + {п2х2) -f /)

{п!х!) -f Сорт!2 {{п2х2) -f f) если х! < х2 {п!х2) -f {п2х!) -f f иначе.

Аналогично определим

4. Взбалт{!)-=Сорт!2{!), Сорт12{!))

и получим главную рекурсию

5. Взбалт {{пх) -\-{ту)-\- f)

{и, {пх) + V)

где {и, V) = ((my) -f / Сорт 12 {{ту) + f),

Сорт! 2 {{ту)+ f)) если X <у {Ложь, {пу) -f {тх) -f f) иначе

Развертка с использованием (3), перестройка условия, развертка с использованием 5.4.2(7), упрощение конъюнкции и обобщение. <={и, {nx)-{-v)

где {и, v) = Взбалт {{ту) + /) если х< у {Ложь, {пу)-\-{тх)-\-1) иначе

Свертка с (4),