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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
II фаза. Слияние.
Файл C очищается. Серии элементов с одинаковыми номерами в файлах A и
B сливаются в одну серию с помощью алгоритма слияния двух упорядоченных
последовательностей в одну и дописываются в конец файла C.
C: 12 23 │ 49 96 │ 14 69 │ 28 73
II шаг. В каждой серии – два элемента.
I фаза. Разделение.
A: 12 23 │ 14 69
B: 49 96 │
28 73
II фаза. Слияние.
C: 12 23 49 96 │ 14 28 69 73
III шаг. В каждой серии – четыре элемента.
I фаза. Разделение.
A: 12 23 49 96
B: 14 28 69 73
II фаза. Слияние.
C: 12 14 23 28 49 69 73 96
Заметим, что в каждой фазе совершается один последовательный проход по
каждому файлу. Отметим также, что если количество элементов в файле C равно
n, то количество шагов алгоритма равно
n
2
log . Поскольку на каждом шаге со-
вершается два прохода по файлу C с n элементами, то количество операций при
сортировке слиянием имеет временную сложность
nn
2
log
⋅
(как и для быстрой
сортировки).
Четырехленточная однофазовая сортировка слиянием
В предыдущем алгоритме вторая фаза неэффективна – данные просто пере-
писываются из одного файла в другой. От этой фазы можно избавиться, введя до-
полнительную ленту (файл). Для этого на фазе слияния следует записывать дан-
ные не в один файл, а попеременно в два, а затем использовать эти файлы в каче-
стве исходных
на следующем шаге.
Пусть первоначально файл C содержит те же данные, что и в предыдущем
пункте.
C: 23 12 49 96 14 69 73 28
На первом шаге данные из файла C следует разбить на два файла, попеременно
записывая их в файл A и файл B:
A: 23 │ 49 │ 14 │ 73
B: 12 │ 96 │ 69 │ 28
Произведем слияние серий. Серии с нечетными номерами будем сливать
в первый
файл, с четными – во второй.

Страницы