Методы программирования. Громов Ю.Ю - 70 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

70
M3. [Цикл по i.] Для всех i, таких, что 0 ≤ i < N – d и i ∧ p = r, выпол-
нить шаг М4. Затем перейти к шагу М5. (Здесь через i ∧ p обозначена
операция «логическое и» над двоичными представлениями чисел i и p.
Так, например, 13 ∧ 21 = (1101)
2
∧ (10101)
2
= (00101)
2
= 5. К этому момен-
ту d – нечётное кратное р (т.е. частное от деления d на р нечётно); а p –
степень двойки, так что i ∧ p ≠ (i + d) ∧ p; отсюда следует, что действия
шага М4 можно выполнять при всех нужных значениях i в любом поряд-
ке или далее одновременно.)
М4. [Сравнение/обмен R
i+1
и R
i+d+1
.] Если K
i+1
> K
i+d+1
, то поменять
местами записи R
i+1
и R
i+d+1
.
M5. [Цикл по q.] Если q ≠ p, то выполнить присваивания d ← q – p,
q ← q
/
2, r ← p и вернуться к шагу M3.
M6. [Цикл по p.] (К этому моменту перестановка K
1
, K
2
, …, K
N
будет p-упорядочена.) Присвоить p ←
2/p
. Если p > 0, то вернуться к
шагу М2. ■
Заметим, что в методе Бэтчера последовательность сравнений пре-
допределена, т.е. каждый раз сравниваются одни и те же пары ключей,
независимо от информации о файле, которую можно получить из преды-
дущих сравнений.
Обратимся к другой стратегии, в которой результат каждого сравне-
ния определяет то, какие ключи сравнивать следующими. Такая страте-
гия не годится для параллельных вычислений, но может оказаться плодо-
творной для вычислительных машин, работающих последовательно.
Рассмотрим схему сравнений/обменов этой стратегии. Пусть имеют-
ся указатели i и j, причём вначале i = 1, а j = N. Сравним ключи K
i
, K
j
и
если обмен не требуется, то уменьшим j на 1 и повторим этот процесс.
После первого обмена увеличим i на 1 и будем продолжать сравнения,
увеличивая i, пока не произойдёт ещё один обмен. Тогда опять уменьшим
j и т.д. Таким образом, будем «сжигать свечку с обоих концов» до тех
пор, пока i не станет равно j. Посмотрим, например, что произойдёт с
нашим файлом из шестнадцати чисел:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
503
87 512
61 908
170
897
275
653
426
154
509
612
677
765
703
уменьшение j и 1-й обмен
154
87 512
61 908
170
897
275
653
426
503
509
612
677
765
703
увеличение i и 2-й обмен
154
87
503
61 908
170
897
275
653
426
512
509
612
677
765
703
уменьшение j и 3-й обмен
154
87
426
61 908
170
897
275
653
503
512
509
612
677
765
703

Страницы