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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

67
Упражнения
1. Используя алгоритм S сортировки простыми вставками, отсорти-
ровать следующую последовательность из двенадцати записей (5 «И»),
(7 «,»), (9 «употреблённое»), (12 «не»), (5 «сало»), (15 «меру»), (18 «,»),
(21 «может»), (12 «в»), (28 «.»), (27 «вред») и (22 «причинить»), в кото-
рых цифры обозначают ключи, а строки символы после цифр – сопутст-
вующую информацию в записях.
2. С помощью алгоритма D сортировки с убывающим шагом отсор-
тировать одиннадцать записей: (101 «сам»), (85 «человека»), (25 «ро-
бей»), (113 «.»), (48 «врагом»), (32 «перед»), (59 «,»), (99 «он»), (11 «Не»),
(60 «лютейший») и (72 «враг»), используя при этом последовательность
шагов 5, 3, 1.
3. Определить по правилу (48) разумную последовательность шагов
для алгоритма D сортировки с убывающим шагом при N = 20 000.
4. Используя графическую иллюстрацию формируемого цикличе-
ского списка, выполнить алгоритм L сортировки вставками в список
применительно к последовательности записей: (4 «В»), (47 «известных»),
(85 «.»), (35 «жильцов»), (76 «обрящешь»), (21 «без»), (55 «насекомых»),
(69 «не»), (12 «доме»).
12. ОБМЕННАЯ СОРТИРОВКА
Семейство алгоритмов обменной сортировки предусматривает сис-
тематический обмен местами элементов пар, в которых нарушена упоря-
доченность до тех пор, пока таких пар не останется.
Наиболее очевидным способом обменной сортировки является ме-
тод пузырька. Он предполагает вначале сравнение ключа K
1
c ключом K
2
и обмен местами записей R
1
и R
2
, если эти ключи не упорядочены. Затем
подобное проделывается с записями R
2
и R
3
, R
3
и R
4
, и т.д. Отметим, что
при выполнении этой последовательности операций записи с большими
ключами будут продвигаться вправо и запись с наибольшим ключом
займёт положение R
N
. При повторном выполнении этого процесса соот-
ветствующие записи попадут в позиции R
N–1
, R
N–2
и т.д., так что все запи-
си будут упорядочены. Метод получил своё название, потому что боль-
шие элементы, подобно пузырькам, «всплывают» на соответствующую
позицию в противоположность методу простых вставок, в котором эле-
менты «погружаются» на соответствующий уровень.
Первый просмотр шестнадцати традиционных ключей, записанных
в порядке снизу вверх, повлечёт тринадцать обменов:

Страницы