|
Главная -> Теоретическое программирование 0 1 2 3 4 5 6 7 [8] 9 10 11 Для Сортировки Обменом мы ограничим Перест! так, чтобы за один вызов устранялось как можно больше инверсий, а для Сортировки Взбалтыванием так, чтобы устранялась одна инверсия за вызов. Более точно, для Обмена имеем 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), 0 1 2 3 4 5 6 7 [8] 9 10 11 0.0187 |
|