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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

69
После каждого просмотра все записи, начиная с последней, которая
участвовала в обмене и выше, занимают свои окончательные позиции,
так что их не нужно проверять при последующих просмотрах. Под такой
группой записей на рисунке поставлена черта. Последним просмотром
следует считать просмотр, при котором не было произведено ни одного
обмена.
Алгоритм В. (Метод пузырька.)
Записи R
1
, …, R
N
переразмещаются на том же месте. После заверше-
ния сортировки их ключи будут упорядочены: K
1
≤ … ≤ K
N
.
В1. [Начальная установка BOUND.] Присвоить BOUND ← N.
(BOUND – индекс самого верхнего элемента, о котором еще не известно,
занял ли он уже свою окончательную позицию. Таким образом, к этому
моменту еще ничего не известно.)
В2. [Цикл по j.] Присвоить t ← 0. Выполнить шаг В3 для j = 1, 2, …,
BOUND – 1 и перейти к шагу В4.
В3. [Сравнение/обмен R
j
и R
j+1.
] Если K
j
> K
j+1
, то поменять местами
R
j
и R
j+1
, а также t ← j.
В4. [Были обмены?] Если t = 0, то завершить работу алгоритма; в
противном случае BOUND ← t и вернуться к шагу В2. ■
Минимальное, среднее и максимальное время работы этого алго-
ритма оценивается последовательностью (min (8N + 1)
u, ave (5.75N
2
+
O(N lnN))
u, max (7.5N
2
+ 0.5N + 1)
u).
Параллельной сортировкой Бэтчера называется обменная сортиров-
ка, в которой сравниваются подбираемые пары несоседних ключей. По-
следовательность сравнений, предназначенную для отыскания возмож-
ных обменов, открыл К.Е. Бэтчер в 1964 г. В его далеко не очевидном
методе, требующем весьма сложного доказательства, выполняется отно-
сительно мало сравнений.
Схема сортировки Бэтчера несколько напоминает сортировку Шел-
ла, но сравнения выполняются по-другому так, что, по существу, проис-
ходит слияние пар отсортированных последовательностей. Поэтому ал-
горитм Бэтчера называют ещё обменной сортировкой со слиянием.
Алгоритм М. (Обменная сортировка со слиянием.)
Записи R
1
, …, R
N
переразмещаются на том же месте. После завер-
шения сортировки их ключи будут упорядочены: K
1
≤ … ≤ K
N
. Предпола-
гается, что N ≥ 2.
M1. [Начальная установка p.] Присвоить р ← 2
t–1
, где t =
N
2
log
–
наименьшее целое число, такое, что 2
t
≥ N. (Шаги М2, …, М5 будут вы-
полняться для р = 2
t–1
, 2
t–2
, …, 1.)
М2. [Начальная установка q, r, d.] Выполнить присваивания q ← 2
t–1
,
r ← 0, d ← p.

Страницы