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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

71
увеличение i и 4-й обмен
154
87 426
61
503
170
897
275
653
908
512
509
612
677
765
703
уменьшение j и 5-й обмен
154
87 426
61
275
170
897
503
653
908
512
509
612
677
765
703
увеличение i и 6-й обмен
154
87 426
61 275
170
503
897
653
908
512
509
612
677
765
703
Здесь для того, чтобы выявить значения указателей i и j непосредст-
венно после обменов, ключи K
i
и K
j
выделены полужирным шрифтом.
Заметим, что в каждом сравнении этого примера участвовал ключ 503.
В общем случае в каждом сравнении будут участвовать исходный ключ K
1
,
потому что он будет продолжать обмениваться местами с другими клю-
чами каждый раз, когда мы переключаем направление. К моменту, когда i
сравняется с j, исходная запись R
1
займёт свою окончательную позицию,
потому что слева от неё не будет больших ключей, а справа – меньших.
В результате исходный файл окажется разделённым таким образом, что
первоначальная задача сведётся к двум более простым: сортировке файла
R
1
, …, R
i–1
и (независимо) сортировке файла R
i+1
, …, R
N
. К каждому из
этих подфайлов можно применить тот же самый метод.
Ниже показано, как выбранный нами для примеров файл полностью
сортируется при помощи этого метода за одиннадцать стадий.
1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
(l, r) Стек
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
(1, 16)
–
154
87
426
61
275
170
503
897
653
908
512
509
612
677
765
703
(1, 6)
(8, 16)
61
87
154
426
275
170
503
897
653
908
512
509
612
677
765
703
(1, 2)
(4, 6),
(8, 16)
61
87
154
426
275
170
503
897
653
908
512
509
612
677
765
703
(4, 6)
(8, 16)
61
87
154
170
275
426
503
897
653
908
512
509
612
677
765
703
(4, 5)
(8, 16)
61
87
154
170
275
426
503
897
653
908
512
509
612
677
765
703
(8, 16)
–
61
87
154
170
275
426
503
703
653
765
512
509
612
677
897
908
(8, 14)
–
61
87
154
170
275
426
503
677
653
612
512
509
703
765
897
908
(8, 12)
–
61
87
154
170
275
426
503
509
653
612
512
677
703
765
897
908
(8, 11)
–
61
87
154
170
275
426
503
509
653
612
512
677
703
765
897
908
(9, 11)
–
61
87
154
170
275
426
503
509
512
612
653
677
703
765
897
908
(9, 10)
–
61
87
154
170
275
426
503
509
512
612
653
677
703
765
897
908
– –
Здесь в скобки заключены подфайлы, которые ещё предстоит отсор-
тировать. В вычислительной машине эти подфайлы можно представлять
парой (l, r), содержащей указатели границ рассматриваемого в данный
момент файла, а также стеком дополнительных пар (l
k
, r
k
), которые ещё
предстоит рассмотреть. Каждый раз, когда файл подразделяется, в стек

Страницы