Основные случаи проходят гладко, и мы получаем алгоритм S4, Сортировка Вставками.

S4 Сорт (Ф) <= {Ф}

Сорт (д: + Z) и СлияниеС {{{1х)}, f, [{{1х)) U f])

fCopT(X)

СлияниеС {Ф, Ф, Ф) {Ф} СлияниеС {{{1х)}, Ф, « + Ф)

{{{пх)}} СлияниеС (Ф, {п2х2) + f2, « + N)

{{пх2) + f2 I /2 е СлияниеС (Ф, /2, Л)} СлияниеС {{{1х)}, {п2х2) + /2, п + ЛГ)

{(плг) + fl I /Г е СлияниеС (Ф, («2л;2) +

+ f2, N)}

если л: < x2 {(ttJ*:2)+f2lf2e СлмянмеС({(/л;)}, f2, N)} иначе.

5.4. Синтез РЗ, Сортировки Обменом и Сортировки Взбалтыванием из Р

В этом разделе мы рассматриваем класс алгоритмов, принципом работы которых является перестановка соседних элементов массива в случае возникновения локальных инверсий. Мы синтезируем варианты наиболее известных алгоритмов из этого класса. Сортировку Обменом и Сортировку Взбалтыванием.

5.4.1. РЗ из Р. В предыдущих двух разделах мы пользовались следующим определением множества всех перестановок множества.

1. nepecT{X)<={f\fs[X]XX и Биект{f, [X], X)}

2. Биект {f, Y, X)f тотальная взаимно-однозначная функция

из У на X.

В этом разделе мы возьмем несколько иную отправную точ« ку. Теперь Перест берет в качестве аргумента функцию, представляющую массив, и вновь вырабатывает множество всех перестановок, т. е.

2. Перест (f) <= {f, f, S Область (f) X Образ (f)

и Биект if I, Область if), Образ (f))},

где Биект определен как прежде.

Ключ к построению рекурсии для вычисления Перест(f) состоит в том, что сначала синтезируется другая функция Перест 1(f), которая вычисляет некоторое подмножество Пе-рестЦ). Неформально HepecTlif) вычисляет все перестановки/.

которые можно получить, двигаясь вдоль f и переставляя или не переставляя соседние элементы. Таким образом, элементы могут свободно перемещаться вправо, но не более чем на одну позицию влево. Теперь мы можем точно охарактеризовать Перест!.

4. Перест! (f) <= {f, f, s Область (f) X Образ (/)

и Биект (f и Область if). Образ (f)) и РядомЦи !)}

5. Рядом{и, f)<Y{nx)fi- ! Г(х)п + !.

В разд. 6.8 МЫ увидим, где возникает это определение Перест!.

Мы имеем

6. Перест! (Ф)<={Ф} Конкретизация (4) и развертка.

7. Перест! {{пх)-{-Ф){{пх)-{-Ф} Конкретизация (4) и развертка.

8. Перест! {{п!х!) + {п2х2) + f)

{/i I/, S Область ({nix!) + {п2х2) + f) X Образ {{п!х!)+

и Биект if и Область{{п!х1)-\-{п2х2) + 1),

Образ {{nlxl) + {п2х2) + /)) и Рядом {fu {nlxl) + {п2х2) + /)}.

Продвижение этих двух фильтров (см. разд. 6.8) приводит нас к {N = п2-\-Область {f)).

9. Перест! {{nlxl) + {п2х2) + /)

<={{n]x!)-\-f,\f,NXx2-\-X

и Биект {fl, N, х2-\-Х) и Pядoм{fu {n2x2) + f)}

[i{{n!x2) + f2\f2NXx! + X

и Биект {f2, N, х! +Х) и Рядом (f2, {п2х1) + f)}

<= {{nlxl) + / , If, S Oблacть{{n2x2)+f)XOбpaз{{n2x2)+f) и Биект if I, Oблacть{{n2x2) + f),

06pa3{{n2x2)-\-f)) и Рядом {fl, {n2x2)-\-f))

и {{n!x2) + /21 /2 S Область {{n2x!)-\-f) X Образ {{n2x!)-\-f) и Бме/ст (/2, Область ({п2х1) -f f),

06pa3{{n2x!)-\-f)) и Ряаож (/г, <«2л;/) + f)} Использование определений Области и Образа

<= {{nlxl) + f 11 f, S Яересг/ ««2jc2) + f)} и {{nlx2) + /21 /2 s Яерест/ ((п2л:/) + f)} Свертка с (4).

Как получить Перест из Перест!} Ключ к разгадке нам дает небольшое размышление о цели алгоритмов сортировки. Оба они осуществляют как бы замыкание, многократно вызывая процедуру перестановки соседних элементов до тех пор, пока не будет достигнут упорядоченный список.

Вначале определим Перест2 как расширение Перест! на множество.

10. Перест2{5) U Перест! (f).

Решающее значение имеет лемма о том, что неподвижная точка Перест2 совпадает с Перест, т. е. Перест2{8) = 88 = = Перест if) для всех / е S, а это ясно из определения Перест, Перест! и Перест2, (3), (4), (5) и (10). Таким образом, мы можем модифицировать (10):

п. Перест2{8)<=ест U Перест! {f) = S

то S

иначе Перест2 U Перест! if)" •)

и записать

12. Перест if <=Перест2{{[}) Мы получили алгоритм РЗ

РЗ Перест (/) Перест2 ({/})

Перест2{3) если u = S то S

иначе Перест2{и)

где м =

J Перест! (f)

Перест! (Ф) {Ф}

Яерест/ {{{пх)}){{{пх)}}

Перест! {{п1х!) + <n2x2) + /)

Kn/x;) + f, I f, е Перест! ({п2х2) + /)} и {{п1х2) + /г I /г е Яересг/ ((п2х/) + /)}.

5.4.2. Сортировка Обменом из РЗ. Определим Сорт как обычно (только на этот раз в качестве аргумента она получает массив)

1- Сорт(1) Упоряд{Перест(f))

где Упоряд определено как в 5.2.2(2), а Перест -в РЗ . Для получения Сортировки Обменом и Сортировки Взбал-тШшием наложим на Перест! такие ограничения, чтобы производились перестановки только в сторону упорядочения списка.

) Здесь автор использует обычную нотацию условных выражений. - Прим. перев.