и мы получаем наш вариант Сортировки Взбалтыванием в виде алгоритма S6.

S6 Сорт (/) если и то f

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

где {и, v) - Взбалт (/) Взбалт{Ф) (Истина, Ф) Взбалт {{(пх)}) -<= (Истина, {(пх)}) Взбалт {(пх) + (ту) + /)

{и, (пх) + у)

где (м, у) = Взбалт {(ту) + /) если х <,у {Ложь, (пу) + (тх) + /) иначе.

6. ПОДРОБНОСТИ

6.1. Имеем

Перест! {N, Х) if \fs U {NXY)U{N,X{X-Y))

и Биект {f, N, Z)}

и Биект{Uf, N, X)}

Правило RS3.

Рассмотрим произвольные подмножества Yl, Y2cz,X, такие, что Yl ф Y2, и произвольные fl, f2, такие, что s {N" X Yl) U и {N, X{X- Yl)), a f2 s (iV X Y2) U (Af, X (X - Y2)). Функция /7 отобразит на элемент xl, такой, что xlYl, xl gY2 некотр-)ый элемент из N, а f2 - некоторый элемент из ЛГ, поэтому ,l\jf2 не удовлетворяет условию биективности, и предыдущее можно переписать как

ух (V X У) и {N, Х{Х- Y))

и Биект {f, N. X) {fl\]f2\fl{N>XY)

f2s{N,X{X-Y))

и BueKT{!l\}f2, N, X)}

Правило RS3.

Чтобы произвести свертку и получить рекурсию для Перест1, необходимо разложить SueKT{fl [} f2, N, X). Но мы знаем, что объединение двух функций с непересекающимися областями определения и областями значений биективно тогда и только тогда, когда обе функции биективны {N = N>[) Nk). Поэтому

МЫ имеем

Биект ifl [jf2, N, X) Биект (fl, N\ У)

и Биект if 2, Nk, Х-У) для любого F S Л".

Это позволяет нам переписать предыдущее как

Перест! {N, Х) [] {f!Uf2\f!NXYu Биект {fl, N\ У)

f2sNkXiX-y) и Биект{f2, N,

Х-У)}.

6.2. Мы имеем

CopTl(N, Х) Упоряд ( и {f! и f2\f! Перест! {N\Y)

f2 е Перест! (N, X - F)})

и {fiUf2\f! Перест! {N\ У)

f2 e Перест! {Nk, Х - У)я Упор

{flUf2)})

используя тот фгкт, что Упоряд {X![j Х2)= Упоряд {X!)[j у no-ряд {Х2), и производя развертку. Чтобы произвести свертку с 5.2.2 (5), мы должны разложить Упор{1! [jf2). Заметим, что

(i) Уп! е ЛА*, n2Nk-nl< п2

(ii) Vf; е Перест! {N\ У), f2 е Перест! {Nk, X - У).

Образ{f!) = y. Образ{12) = Х-У Область {fl) = N\ Область {f2) = Nk-

Поэтому, если только не Vy е F, л: е Z - F • г/ < л:, то найдутся {п1у!) е fl, {п2у2) е f2, такие, что п! < п2, а у! > у2, т. е. не Упор {f! и f2). Если У таково, то Упор {f! [}f2)<= Упор {fl) и Упор {f 2). Условие VyeF, хХ - У у<х запишем как У < X - У и перепишем предыдущее как

и {f!Uf2\f! Перест! {N\ У) и Упор {fl)

YX-Y

f2 е Перест! {Nk. {Nk, Х-У) я Упор {f2)}.

6.3. Начнем с

CopT{N, X)-i= Упоряд {Перест {N, X))

{{пере {N), у) + / I / е Перест! {ост {N), X - {у})

к Упор {{пере {N), у)+ f)} Развертка с использованием Р! и 5.2.2(2).

Так как нам известно, что VnocT{N), nepe{N)<. п, то из рассуждений, подобных приведенным в 6.2, можно видеть, что если только у не выбран таким, что Vx X- {у}-у <, х, все компоненты объединения будут Ф. Для такого у мы также имеем

Упор {{пере {N), y) + f) Упор (/)

(так как f Перест! {oct{N), Х-{у}),

и поэтому

Сорт1 {N, X) {{пере {N), y) + f\f Перест! {ост {N), X - {у})

и Упор{П}

для некоторого у такого что у Х и Ул; е Х-{у}, у <х.

6.4. Мы имеем

Слияние 1 {{nlxl) + fl, {п2х2) + f2, + N)

{/ I f s tt + X Образ {{nlxl) + fl) и Образ {{п2х2) + /2) и Биект {f, n + N, Образ {{nlxl) + fl) [J06pa3{{n2x2) + f2)) и Регуляр {f, {nlxl)-\-fl) и Регуляр (f, {п2х2)-\-f2)}.

Обозначив 06pa3{fl) - XI, a 06pa3{f2) = X2, перепишем это как

{f\fsn+NXxl-\-Xl[}x2 + X2

и Биект{f, n-\-N, х1-\-Х1[]х2 + X2) и Регуляр {f, {nlxl) + fl) и Регуляр {f, {n2x2) + f2)}.

Теперь перед нами встала задача редукции декартова произведения. Предыдуш,ее приводится к виду

{f I f S {пх 1) + {{п}ХХ1)[} {пх2) + ({«} X Х2)

\}NX{xl}\]NXXl\]NX{x2}\]NXX2 и Биект{f, n-\-N, х1-\-Х1\]х2-\- Х2) и Регуляр (/, {nlxl) + fl) и Регуляр (/, {п2х2) + /2)}

Используя правило RC3. { и /2 и f3 и f и /5 и /6 и f7 и f8 I

S {{nxl)}, f2 {п} X XI, f3 S {{пх2)}, 14 S {«} X Х2 f5sAfX№ f6NXXl, f7NX{x2}, f8sNXX2 и Бме/сг {fl и /2 и /5 и f4 U /5 U f6 U /7 U fS,

n + N, xl-\-Xl[ix2 -{-X2) и Регг/ллр ( U f2 U /5 U f4 U /5 U /6 U f7 U {nlxl)+fl) и Регг/ляр (f/ U f2 U f5 U f U f5 U f6 U f 7 U f8,

{n2x2)-\-f2)}

Используя правило RS3.