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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

62
COUNT
6 1 8 0 15
3 14
4 10
5 2 7 9 11
13
12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
и, например, величина COUNT[3] + 1 = 9 определяет окончательное по-
ложение записи R
3
с ключом 512.
Время работы алгоритма C изменяется в пределах от (3N
2
+ 10N – 4)u
до (5.5N
2
+ 7.5N – 4)u в зависимости от исходной последовательности
ключей. Среднее время работы находится где-то посередине. Множитель
N
2
в выражениях свидетельствует о том, что алгоритм не даёт эффектив-
ного способа сортировки при больших значениях N.
Рассмотрим ещё одну разновидность сортировки посредством под-
счёта. Она эффективна в том случае, когда имеется много равных клю-
чей, и все они попадают в достаточно узкий диапазон.
Алгоритм D. (Распределяющий подсчёт.)
Этот алгоритм сортирует записи R
1
, R
2
, …, R
N
, в которых все ключи
целые и лежат в диапазоне [u, v]. Он использует вспомогательную табли-
цу COUNT[u], …, COUNT[v] и в конце своей работы все записи в требуе-
мом порядке переносит в область вывода S
1
, S
2
, …, S
N
.
D1. [Сброс счётчиков.] Установить значения COUNT[u], …,
COUNT[v] равными нулю.
D2. [Цикл по j.] Выполнить шаг D3 при 1 ≤ j ≤ N, а затем перейти к
шагу D4.
D3. [Увеличение COUNT[K
j
].] Увеличить значение COUNT[K
j
] на 1.
D4. [Суммирование.] (К этому моменту значение COUNT[i] есть
число ключей, равных i.) COUNT[i] ← COUNT[i] + COUNT[i – 1] для
i = u + 1, u + 2, …, v.
D5. [Цикл по j.] (К этому моменту значение COUNT[i] есть число
ключей, меньших или равных i, в частности COUNT[v] = N.) Выполнить
шаг D6 для j = N, N – 1, …, 1 и завершить работу алгоритма.
D6. [Вывод R
j
.] i ← COUNT[K
j
], S
i
← R
j
, COUNT[K
j
] ← i – 1. ■
При сформулированных выше условиях это очень быстрая процеду-
ра сортировки.
Упражнения
1. Используя алгоритм C, отсортировать записи, которые образуют
последовательность ключей 5, 0, 5, 0, 9, 1, 8, 2, 6, 4, 1, 5, 6, 6, 7, 7. Уста-
новить, является ли сортировка по алгоритму C устойчивой.
2. С помощью алгоритма D отсортировать записи 5 T, 0 C, 5 U, 0 O,
9 ., 1 N, 8 S, 2 R, 6 A, 4 A, 1 G, 5 L, 6 T, 6 I, 7 O и 7 N, в которых цифры
обозначают ключи, а символы после цифр – сопутствующую информа-
цию в записях.

Страницы