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

UptoLike

ВУЗ: 

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

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

Рубрика: 

21
C: 12 23 │ 14 69
D: 49 96 │ 28 73
Повторим слияние серий, используя полученные файлы в качестве исходных.
A: 12 23 49 96
B: 14 28 69 73
На последнем шаге полученные два файла следует слить в один, записав элемен-
ты второго файла в конец первого.
C: 12 14 23 28 49 69 73 96
Отметим, что на каждом шаге по каждому файлу мы совершаем один после-
довательный проход.
Естественное слияние
В двух предыдущих алгоритмах не учитывается упорядоченность элементов.
Эти алгоритмы работают одинаковое время для любых последовательностей дан-
ных, в частности, если данные уже отсортированы. Предложим более совершен-
ный алгоритм, в котором учитывается уже имеющаяся упорядоченность элемен-
тов. Такой алгоритм называется естественным слиянием.
Пусть данные находятся в файле C. Разобьем их на серии упорядоченных
элементов.
C: 17 19 21 │ 13 57 67 │ 23 29 │ 11 59 61 │ 7 31 37 │
2 43 67 │ 5
Применим алгоритм трехленточной двухфазовой сортировки, но в конце ка-
ждой фазы будем разбивать элементы на серии заново.
I шаг.
I фаза. Разделение.
A: 17 19 21 │ 23 29 │ 7 31 37 │ 5
B: 13 57 67 │ 11 59 61 │ 2 43 67
Обратим внимание, что две первых серии в массиве A могут быть объединены в
одну
:
A: 17 19 21 23 29 │ 7 31 37 │ 5
II фаза. Слияние.
C: 13 17 19 21 23 29 57 67 │ 7 11 31 37 59 61 │ 2 5
43 67
II шаг.
I фаза.
A: 13 17 19 21 23 29 57 67 │ 2 5 43 67
B: 7 11 31 37 59 61
II фаза.
C: 7 11 13 17 19 21 23 29 31 37 57 59 61 67 │ 2 5 43
67

Страницы