SRB 1

STA ♦+1(0:2) ENT4 *

LDA INPUT.2 LDX INPUT.3 CMPA INPUT.3 JL IF CMPA INPUT.4 JLE 3F CMPX INPUT.4 JG 4F

rA rXi

тА:Ь

тХ:Ь

2Н ENTA 0.2 STA INPUT,3 c<b<a JGE 5F

INCA 0.3 STX INPUT.2 CMPX INPUT.4 a<b,c

5HLDA INPUT. 4 гАЬ JGE 5B

JMP 6F LDA INPUT,3 a<c<b

4HLDA INPUT, 3 b<c<a LDX INPUT, 4

-a LDX INPUT,2 STX INPUT.3

-c STX INPUT.3 JMP 6F

JMP 5F 5HLDX INPUT,4 b<a<c

3H STX INPUT.2 c<a<b STX INPUT.2

LDX INPUT, 4 6HLDX INPUT+1.2

STX INPUT.3 STX INPUT.4

JMP 6F ENT4 2,2

IHCMPA INPUT,4 ENT5 0,3

После этого должно следовать STA INPUT+1,2 (см. замечание после (27)). Замените команду в строке 22 командой STX INPUT+1,2. Если в системе команд отсутствует команда поразрядного сдвига, то первые три команды в программе нужно заменить командой ENTX 0.2. INCX 0.3; ENTA 0; DIV =2=.

Сущность этой программы состоит в организации обмена Rt+i с H[(i+r)/2j и сортировки записей Ri, Ri+i и Rr. Затем к Д;+1... Rr-i применяется обычная процедура разбиения. Несколько команд можно сэкономить, просто поместив медианный элемент в регистр гА и переписав Д; туда, где ранее был медианный элемент. Далее все нужно продолжить, как в программе Q. Но такой подход может привести к нежелательным последствиям, поскольку требуется порядка Л шагов для сортировки массива N-1 ... 1. (Этот неожиданный побочный результат впервые подметил Д. Б. Колдрик (D. В. Coldrick), но его нужно проверить самостоятельно. Попробуйте!) Рекомендуемый выше метод, авторство которого принадлежит Р. Седгевику, оказался свободным от связанной с длиной слова аномалией, но работает так же быстро. При использовании такой схемы не нужно проверять Ко и Kn+1. Следовательно, проверка граничных значений не сдерживает скорости выполнения внутреннего цикла.

56. Можно решить рекуррентное соотношение {1)хп = Ьп + 2 E*=i( - 1)(п - fe)x/t-i при п > т, положив Уп = пхп, Ип = пуп+i - {п + 2)уп, Vn = nun+i - (n - 5)u„. Отсюда Vn = 6{bn+2 - 2bn+i +bn) при n > т. Например, пусть Xn = <5ni при n < m и пусть b„ = 0. Тогда Vn = О при всех n > m; следовательно, n-Un+i - m-Um+i- Поскольку j/m+i = 12/m и !/m+2 = 12/(m-1-1), окончательно находим Xn = {n+l)/m{m+l){m + 2) + y-(m-l)-/n-при n > m. В общем случае пусть Д = (l2/(n - l)(n - 2)) E*=i( ~ 1)(" ~ k)xk-i; если 6„ тождественно равно О, то решением при п > т будет

((т + 1)/т+2 -{т + 3)/m+i) т 7пв

Хп = {п+1)

(т + 1)/т+2 - (т - 4)fm + l

7{т + 1){т + 2)

Если Ьп = (з) /п£ и х„ = О при п < т, то решением будет

Хп (р-3)(р-2) 12 1 12 (m+1-p)

п + 1 (р б)(р+1)(п + 1) 7(p + l)(m + 2)£+i 7 (р-6)(п + 1)1

при п > т. За исключением случаев, когда р = -1, получим Хп/{п + 1) = -("+1 ~ Ят+2) + i + (т + 2)V(n + 1), а когда р = 6, х„/(п + 1) = -f{Hn-6 - Нт-ь)/{п+1) + i/(m + 2)+i/(n+l).

Рассуждая, как в упр. 21-23, придем к выводу, что первая фаза разделения теперь внесет 1вА, ЬвВиМ-1вС, где t определяется, как и ранее, но после перекомпоновки, которая сделана в упр. 55. При новых предположениях bstN = 6(*) (~/~)/A(ri).

Следовательно, рекуррентные соотношения, выведенные выше, в этой задаче появляются следующим образом.

Значения Ьлг/()

для N < М для N > М Решения для N > М

AнaлoгичнoSN = f (iV+1)(5M+ 3)/(2M+ 3)(2M + 1) - 1 + 0(iV-*). В среднем суммарное время выполнения программы в упр. 55 равно 53An + IIjBn + 4Cn + 3Dn + 8En + 9Sn + 7N. Выбор M = 9 лишь немного лучше, чем Л/ = 10, и приводит к среднему времени выполнения, равному примерно lOffiVlniV + 2.116iV [Acta. Inf. 7 (1977), 336-341]. После замены SRB на DIV IIAn добавляется к среднему времени выполнения и требует установить М = 10.

РАЗДЕЛ 5.2.3

1. Нет, но метод, в котором используется оо (описанный непосредственно перед алгоритмом S), устойчив.

2. Просмотр линейного списка, хранящегося в последовательных ячейках памяти, часто выполняется несколько быстрее, если двигаться в сторону убывания индексов, поскольку, как правило, легче проверить, равен ли индекс О, чем проверить, превышает ли он N. (По той же причине при поиске на шаге S2 индекс убывает от j к 1; тем не менее см. упр. 8!)

3. (а) Перестановка ai... un-iN соответствует исходным массивам

Na2 .. .un-iai, oiNas .. алг-1 02, oi 02 ... on-2Aoa-i, ai... un-iN

(b) Как показано в разделе 1.2.10, на первой итерации шага S2 число случаев изменения максимума равно Hn - 1- [Следовательно, Bn можно найти из соотношения 1.2.7-(8).]

4. Если исходный файл является перестановкой множества {1, 2,... ,N}, то число случаев, когда на шаге S3 окажется i = j, в точности на единицу меньше числа циклов в этой перестановке. (В самом деле, нетрудно показать, что на шагах S2 и S3 элемент j попросту удаляется из своего цикла. Следовательно, шаг S3 бесполезен лишь в том случае, если элемент j был наименьшим в своем цикле.) Согласно равенствам (1.3.3-(21)) можно было бы сэкономить в среднем Hn - 1 из N - 1 выполнений шага S3.

Таким образом, было бы неэффективно вставлять перед шагом S3 дополнительную проверку "г = j?". Вместо того чтобы сравнивать i с j, можно слегка удлинить программу для шага S2, продублировав часть команд, чтобы не переходить к шагу S3, если первоначальный выбор Kj не изменился во время поиска максимума. За счет этого программа S стала бы работать чуть-чуть быстрее.

5. {N-l} + {N-3)+-- = [iVV4J.

6. (а) Если на шаге S3 окажется, что i / j, то после его выполнения число инверсий уменьшится на 2т - 1, где т на единицу больше числа ключей, лежащих в интервале между Ki и Kj среди Ki+i ... Kj-i. Ясно, что m не меньше, чем вклад в значение параметра В на предыдущем шаге S2. Примените теперь следствие из упр. 4, связывающее циклы с условием i = j. (b) Любую перестановку можно получить из N.. .2 1 путем последовательных взаимообменов соседних элементов, которые нарушают исходное упорядочение. (Примените в обратной последовательности те обмены, под действием которых

перестановка сортируется в порядке убывания.) Каждая такая операция уменьшает / на единицу и изменяет С на ±1. Следовательно, ни для одной перестановки значение I - С не превосходит соответствующего значения для N.. .2 1. [Из упр. 5 вытекает, что неравенство В < lN/4] - наилучшее из возможных.]

7. В работе А. С. Yao, On straight selection sort (Computer Science Teclinical Report 185, Princeton University, 1988), показано, что дисперсия равна aN + 0{N logN), где q = \/7г1п Ri 0.9129. В ней также высказано предположение, что в действительности составляющая ошибки значительно меньше.

8. Можно начинать очередную итерацию шага S2 с позиции Ki, поскольку мы запомнили max(A!"i,..., A!"i i). Один из способов учета всей этой дополнительной информации - использование таблицы связи Li... Ln, такой, что равно предыдущему выделенному элементу всякий раз, когда Кк также выделено; Li = 0. [Тот же результат можно получить, используя меньший объем дополнительной памяти, "заплатив" за это лишней операцией сравнения.]

В приведенной ниже НХХ-программе применяется модификация адреса в ходе вьшолнения, которая ускоряет реализацию внутреннего цикла. Исходное состояние регистров таково: г11 = j, т12 = к - j, rI3 = i, тА = Ki.

01 02 03 04 05 06 07 08 09 10 11 12 13

Ц 15 16 17 18 19 20 21 22 23 24 25 26 27 28

START ENTl STZ

8H 6H

LINK+1 JMP 9F STl 6F(0:2) ENT4 INPUT,1 ST4 7F(0:2) ENT4 LINK,1 ST4 8F(0:2) CMPA INPUT+J,2 JGE .+4

LINK+J,2 J,2

INPUT,3 1

J2NP 7B LDX INPUT,1 INPUT,3 INPUT,1 1

0,3 LINK,3

ST3 ENT3 LDA INC2

STX STA DECl ENT2 LD3 J3NZ 5F ENT3 1 ENT2 2 DEC2 0,1 LDA INPUT,3 J2NP IB JIP 4B

1 1 1

N-D N-D N-D N-D N-D

N+l-C N+l-C N + l-C

С N + l N + l N+l D + 1

N.

Модификация адреса во внутреннем цикле.

Переход, если Ki > Кк. Иначе - Lk +- i. i +- к.

к+-к+1.

Переход, если к < j.

[Адрес модифицирован]

[Адрес модифицирован] [Адрес модифицирован]

Ri < rI2-

- предыдущее значение Ri.

J-1-S- i.

i Li.

Если г > 0, A; начнет с i. Иначе - i +- 1. к начнет с 2.

гА Ki.

Переход, если к < j. Переход, если j > 0.

9. - 1 -Н En>*>2 ((* - 1)/2 - 1/*) = И 2 ) + ~ - [Средние значения параметров С и D равны Hn + 1 и Hn - 5 соответственно. Следовательно, среднее время вьшолнения программы равно (1.25iV + 31.75iV - 15Hn + 14.5)u.] Программа Н работает значительно лучше.