C ортировка файлов Програмирование на языке высокого уровня Т.Г.Чурина

последовательностей в одну упорядоченную.

Это можно сделать следующим образом:
сравнить

наименьшие элементы из упорядоченных
последовательностей и наименьший из них перенести в готовую
последовательность.

Далее снова сравнить начала последовательностей и наименьший из
этих элементов добавить в готовую последовательность и т. д.

Как только одна из последовательностей закончится, она исключается
из рассмотрения.

Когда остается только одна последовательность,
ее «хвост» можно просто переместить в готовую.

38 40 51 75
1 15 63 89 101 107
Сравним

первые элементы отсортированных файлов,
наименьший из них запишем в выходной файл:
 8 38 40 51 75
1  15 63 89 101 107
1 
Следующий шаг
8  38 40 51 75
1  15 63 89 101 107
1 8 

второго файлов не
будут переписаны в третий в заданном
порядке.

В результате получим

отсортированный
по возрастанию файл:
1 8 15 38 40 51 63 75 89 101 107

можно применить к сортировке
файлов, а именно два отсортированных файла слить

в
третий отсортированный.

Данный метод слияния был предложен фон Нейманом
в 1945 г. и предназначался именно для сортировки файлов.

разделим входную последовательность на две части,
отсортируем каждую из них

по отдельности,
результаты сольем, как описано выше.

Исходная задача сводится к двум аналогичным задачам с
меньшим объемом данных, применим рекурсию:
— на фазе рекурсивного спуска каждая из образующихся последовательностей делится на две части до тех пор, пока не образуются последовательности длины 0 или 1, которые сортировать не надо;
— на фазе возврата из рекурсии пары уже отсортированных подпоследовательностей сливаются.

подпоследовательности:

al[], int lenl, key a2[], int Ien2, key ar[])
/

* Слияние отсортированных массивов al длины lenl и а2
длины len2 в массив аr */
{ int i=0, j=0, k=0;
key x;
while ((i if (i==lenl) /* 1-я кончилась: берем из 2-й */
х = a2[j++];
else if (j==len2) /* 2-я кончилась: берем из 1-й */
x = al[i++];
else if (al[i] x = al[i++];
else х = a2[j++];
ar[k++] = x;
}
}

sort_merging (key a[], int L, int R)
/* L,R - границы

сортируемой части массива а */
{ int i,M;
М = (L+R)/2;
if (L < M)
sort_merging(a, L, M);
if(M+l < R)
sort_merging(a, M+l,R);
/* слияние частей в aw */
merge(&a[L], M-L+l,&a[M+l], R-M, &aw[L]);
/* копирование в исход.фрагмент */
for (i=L; i<=R; i++)
a[i] = aw[i];
}

поскольку упорядоченные данные должны накапливаться для
последующего слияния в исходном массиве,

приходится дополнительно
переписывать результат на место исходной подпоследовательности.

Нам было бы достаточно иметь в качестве aw локальный рабочий массив
длины R – L + 1, но в Си невозможно описать массив переменной длины
(без обращения к более медленным средствам динамической памяти).

Введение же локального массива максимальной длины N, используемого
лишь частично привело бы к затратам памяти до N log2 N записей, так как
на каждом из log2 N уровней рекурсии в памяти хранился бы отдельный
рабочий массив длины N.

~ 2N записей и в данном случае
организовано корректно:
ни один

элемент массива aw, записанный в функции слияния,
не может быть изменен до переписи его в массив а в функции
сортировки, а после переписи он становится не нужен.

файл f, который нужно
отсортировать.
Заметим, что в функции слияния

merge доступ к
элементам частей массива и к массиву-результату
исключительно последовательный:
индексы-указатели текущего доступа сдвигаются только на
единицу вперед, без возвратов и скачков.
Поэтому операции вида a[i + +] для массива можно заменить
на типовые операции чтения и записи элемента файла с
продвижением к позиции следующего элемента.

части и переписывать в них
элементы. Вместо этого мы устанавливали и

перемещали
два указателя.

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

Таким образом, нужна процедура split, выполняющая
физическое разделение.

число его записей не всегда известно и определение
длины требует дополнительного

холостого считывания.

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

Концом «раздачи» является достижение конца входного файла,
при этом количество элементов в новых файлах отличается
максимум на единицу, что и требуется.

66 4 75 80 31
1 разделение 13 71 99

37 66 75 31 86 52 21 45 4 80
2 разделение 13 99 66 31 71 37 75 86 21 4 52 45 80
3 разделение 13 66 99 31 71 75 37 86 4 21 52 80 45
4 разделение 13 66 99 31 71 75 37 86 4 21 52 80 45

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

которых не нужно
беспокоиться о выборе уникальных имен.

/* упрощенные вызовы файловых функций С */

#define fget(f,x) fread(&x, sizeof(x), 1, f)
#define fput(f,x) fwrite(&x, sizeof(x), 1, f)

f: перепись элементов нечетных позиций в fl, четных - в

f2 */
{ key x;
int n=0; /* счетчик длины файла */
rewind (f); /* возврат к началу разделяемого файла */
fget (f, x);
while (!feof(f)) {
/* (feof срабатывает ПОСЛЕ попытки чтения!) */
fput (fI, х);
fget (f, x);
if (!feof(f)) {
fput (f2, x);
fget (f, x);
}
n++;
}
return n>l; /* false (длина 0 или 1) сигнализирует о прекращении разделения */
}

fl и f2 в fr */
{ key xl, x2;
rewind(f1);

/* перемотка к началу всех файлов */
rewind(f2); rewind(fr);
fget(fl, xl); fget(f2, x2);
while (!feof(fl) || !feof(f2)) {
if (feof(fl)) {
fput(fr, x2); fget(f2, x2);
} else if (feof(f2)) {
fput(fr, xl); fget(fl, xl);
} else if (xl fput(fr, xl);
fget(fl, xl);
} else {
fput(fr, x2);
fget(f2, x2);
}
}
}

должен быть открыт */
{ /* создание временных файлов

для частей */
FILE *fl = tmpfile(),
*f2 = tmpfile();
/* разделение на фазе спуска в рекурсию */
if (split(f, fl, f2)) {
sort_merge(f1);
sort_merge(f2);
}
/* слияние на фазе возврата из рекурсии */
merge(f1, f2, f);
/* закрытие и удаление рабочих файлов */
fclose(f1);
fclose(f2);
}

= fopen("inputfile","r+b"); /* открытие файла */
sort_merge(f); /* сортировка открытого

файла */
fclose(f); /* закрытие выходного файла */
}

файлов остаются теми же,
что и для массивов.
Подсчитаем количество используемой

внешней памяти, равное
суммарной длине всех одновременно существующих файлов.
Исходный файл существует всегда, в нем N элементов.
Оба файла 1-го уровня после разделения тоже существуют всегда, вплоть
до слияния – в них тоже N элементов.
Файлы 2-го уровня существуют не одновременно: те, которые получаются
разделением 1-го файла 1-го уровня, уничтожаются после слияния, и при
переходе ко 2-му фай­лу 1-го уровня занимаемая ими память может быть
переиспользована. Таким образом, на 2-м уровне всегда хранится около
N/2 элементов.
Аналогично, на 3-м уровне хранится N /4 элемента, на k-м — N/2k-1 ,
на последнем [lоg2 N] уровне— 1 элемент.
Окончательно на самом глубоком уровне рекурсии в памяти может
находиться 1 + 2 + 4 + ... + N/2 + N + N ~ 3N элементов.

внешней сортировки оптимизация именно этого важна.

Еще во времена, когда

файлы располагались на магнитофонных лентах, а
«перемотка» означала действительную перемотку катушки, был придуман
двухуровневый способ организации файлов: в виде файла записей, содержащего
собственно данные, и индекс-файла, содержащего короткие записи-пары
«ключ + ссылка». Ключи, это только та информация, сравнением которой
определяется относительный порядок записей, а ссылки — это позиции
в основном файле записей, соответствующих ключам.
При всех операциях поиска и сортировки обрабатываются более короткие
индекс-файлы, а доступ к основному файлу выполняется один раз, когда позиция
требуемой записи становится определена.
При удалении записи обычно удалялся только индекс из индекс-файла, а запись
в файле только помечалась как удаленная. Специально проводимая операция
уплотнения файла выполнялась во время техобслуживания устройств, когда
работы на машине не производились.

Современные машины, конечно, намного производительнее, но возросли и
объемы обрабатываемых данных. Поэтому технологии индексированных файлов
применяются в системах обработки данных до сих пор.

из N
элементов тратится не меньше с  N 

log2 N сравнений
при с > 0, N  .
Обоснование.
Для заданной последовательности из N элементов может
быть построено N! перестановок. Алгоритм сортировки,
устанавливающий путем сравнения пар, какая из этих
перестановок является единственно правильным решением,
фактически осуществляет спуск по так называемому дереву
решений — двоичному дереву, листьями которого являются
решения, а узлами — условия, позволяющие сузить выбор.

последовательности можно построить 6 различных перестановок, которые являются листьями в

представленном дереве решений.

Значит, высота дерева решений  log2 N.
Из неравенства
следует заключение

теоремы, так как

А количество сравнений, которые необходимо сделать, чтобы
получить любую из перестановок примера, не меньше 2 (lоg2 6 ≈ 2.5).