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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

134
3. Выполнение по алгоритму S сортировки простым двухпутевым
слиянием даёт в результате следующую последовательность из пятнадца-
ти записей: (4 «Взирая»), (7 «на»), (10 «солнце»), (13 «,»), (26 «при-
щурь»), (29 «глаза»), (43
1
«свои»), (43
2
«и»), (49
1
«ты»), (49
2
«смело»),
(54 «разглядишь»), (57 «на»), (69 «нем»), (71 «пятна»), (97 «.»).
При этом размещение ключей в двух используемых областях памяти
до сортировки, а также по окончании каждого просмотра было следующим:
До сорти-
ровки
K
j
13
43
26
54
7 57
71
97
69
43
4 49
10
49
29
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
K
j
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
j 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1-й
просмотр
K
j
13
43
26
54
7 57
71
97
69
43
4 49
10
49
29
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
K
j
13
29
10
26
4 7 69
71
97
57
43
54
49
49
43
j 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2-й
просмотр
K
j
13
29
43
49
4 7 43
57
97
71
69
54
49
26
10
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
K
j
13
29
10
26
4 7 69
71
97
57
43
54
49
49
43
j 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
3-й
просмотр
K
j
13
29
43
49
4 7 43
57
97
71
69
54
49
26
10
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
K
j
10
13
26
29
43
49
49
54
97
71
69
57
43
7 4
j 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
4-й
просмотр
K
j
4 7 10
13
26
29
43
43
49
49
54
57
69
71
97
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
K
j
10
13
26
29
43
49
49
54
97
71
69
57
43
7 4
j 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
4. Сортировка посредством слияния списков по алгоритму L даёт в
результате следующую последовательность из пятнадцати записей:
(0 «Память»), (2 «человека»), (3 «есть»), (5 «лист»), (43 «белой»),
(45 «бумаги»), (55 «:»), (66 «иногда»), (67 «напишется»), (70 «хорошо»),
(74 «,»), (83 «а»), (85 «иногда»), (88 «дурно»), (93 «.»).
При этом распределение связей для двух линейных списков перед
началом сортировки, а также по окончании каждого из просмотра было
следующим:
j 0
1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
K
j
–
70
85
66
43
55
67
0 93
3 83
88
5 2 74
45
–
L
j
1
–3
–4
–5
–6
–7
–8
–9
–10
–11
–12
–13
–14
–15
0 0 2

Страницы