Основы программирования. Файлы. Рекурсия - 17 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

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

Рубрика: 

19
второго, будут возвращать пустую строку, а файловый указатель продвигаться не
будет. Кроме того, после прерывания зациклившейся программы на диске оста-
нется большой временный файл $tmp.dat.
В заключение заметим, что данный каркас решения можно использовать и
для родственных задач. Например, если требуется вычислить количество и сумму
чисел в файле (как в
примере 1), то в данном решении достаточно заменить функ-
цию Convert процедурой подсчета количества и суммы чисел в строке и изъять
все строки, связанные со вспомогательным файлом.
2.7 Алгоритмы внешней сортировки
Алгоритмы внешней сортировки – это алгоритмы, позволяющие сортировать
данные во внешней памяти. Они ориентированы на последовательный перебор
элементов и поэтому ранее широко применялись именно для сортировки файлов.
Однако эти алгоритмы могут быть использованы для любых последовательно ор-
ганизованных данных: например, для массивов и списков. Кроме того, данные ал-
горитмы по скорости работы
сравниваются с алгоритмом быстрой сортировки и
потому являются одними из лучших. Реализация этих алгоритмов, однако, явля-
ется достаточно громоздкой, поэтому в настоящем пункте приведем лишь сам ал-
горитм.
Далее будем предполагать, что используемые файлы имеют только последо-
вательный доступ. Сами файлы будем называть также лентами (по аналогии с
лентой магнитофонной
кассеты, доступ к которой может быть только последова-
тельным).
Трехленточная двухфазовая сортировка слиянием
Пусть исходные данные хранятся в файле C, и количество данных есть сте-
пень двойки. Приводимый ниже алгоритм использует на каждом шаге две фазы
(разделение и слияние) и три ленты (файла). Отсюда его название – трехленточ-
ная двухфазовая сортировка слиянием.
Разобьем данные на серии. Серией будем называть группу подряд идущих
отсортированных элементов.
I шаг. На первом шаге в каждой серии будет содержаться один элемент.
C: 23 │ 12 │ 49 │ 96 │ 14 │ 69 │ 73 │ 28
I фаза. Разделение.
Файлы A и B очищаются. Серии в файле C с нечетными номерами записыва-
ются в файл A, а с четными – в файл B.
A: 23 │ 49 │ 14 │ 73
B: 12 │ 96 │ 69
│ 28

Страницы