Сортировка файлов

Главная трудность при сортировке файлов состоит в том, что в данный момент времени программе доступен лишь один элемент данных, записанный в файле. Это и понятно: если файл хранится на магнитном диске (для других устройств ситуация аналогична), магнитные головки не могут одновременно находиться в двух местах и считывать более, чем один элемент файла (Рис. 12.3).

Рис. 16.3.Считывание файла.

Как же быть? Для сортировки файлов используется особый прием – сортировка слиянием. Сортировка заменяется слиянием двух половинок файла. Последовательность действий такова (Рис. 12.4):

1. Делим файл а на две половины: b и c.

2. Сливаем части b и c с упорядочиванием пар

3. Повторить, начиная с п.1

Рис. 16.4. Схема сортировки слиянием.

Рассмотрим пример такой сортировки слиянием (Рис. 12.5). Исходный файл содержит элементы 44, 55, 12, 42, 94, 18, 06, 67. Сначала файл разбивается на два файла, содержащие элементы 44, 55, 12, 42 и 94, 18, 06, 67 соответственно. Далее два файла сливаются в один. При слиянии из каждого файла берется по одному элементу, и они записываются в выходной файл в упорядоченном виде, образуя пары (44 94), (18 55), (06 12), (42 67). Затем процесс повторяется и "двойки" группируются в "четверки" ((06 12 44 94) (18 42 55 67)). Наконец, после еще одного слияния исходный файл оказывается полностью отсортированным.

Неприятная особенность такой сортировки – число элементов в файле должно быть четным. Выход прост: вводим дополнительный фиктивный элемент, если длина фала нечетная, а потом его убираем.

Рис. 16.5. Пример сортировки слиянием.

Сортировка файла естественным слиянием использует тот факт, что файл уже частично упорядочен. Серией называется упорядоченная последовательность элементов файла:

( 12.2)

(математический символ называется "квантор всеобщности" и означает "для каждого". Он происходит от англ. "all").

Естественное слияние основано на правиле: любые две серии m и n можно сразу сливать в новую серию m+n. При этом при каждом проходе по файлу число серий уменьшается вдвое. Поэтому среднее число операций при такой сортировке будет .

Рассмотрим пример сортировки естественным слиянием (Рис. 12.6). Файл из 20 элементов сортируется всего за три прохода – неплохой результат!

Рис. 16.6. Пример сортировки естественным слиянием.