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




НазваниеCортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей
Дата конвертации23.07.2013
Размер445 b.
ТипПрезентации


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


Слияние последовательностей

Под слиянием будем понимать объединение двух или более

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

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

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

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

последовательность.

Далее снова сравнить начала последовательностей и наименьший из

этих элементов добавить в готовую последовательность и т. д.

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

из рассмотрения.

Когда остается только одна последовательность,

ее «хвост» можно просто переместить в готовую.

Объединим два файла в третий (позиция считывания отмечена чертой)

 8 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, которые сортировать не надо;

— на фазе возврата из рекурсии пары уже отсортированных подпоследовательностей сливаются.

Пример



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



Следующая пара функций реализует сортировку слиянием для массивов:

Void merge (key 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;

}

}

static key aw[N]; /* вспомогательный глобальный массив для слияния */

static key aw[N]; /* вспомогательный глобальный массив для слияния */

void 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.

Однако, поскольку упорядоченные данные должны накапливаться для

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

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

Нам было бы достаточно иметь в качестве aw локальный рабочий массив

длины R – L + 1, но в Си невозможно описать массив переменной длины

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

Введение же локального массива максимальной длины N, используемого

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

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

рабочий массив длины N.

Использование глобального массива приводит к оценке затрат

Использование глобального массива приводит к оценке затрат

памяти в данном методе ~ 2N записей и в данном случае

организовано корректно:

ни один элемент массива aw, записанный в функции слияния,

не может быть изменен до переписи его в массив а в функции

сортировки, а после переписи он становится не нужен.

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

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

отсортировать.

Заметим, что в функции слияния merge доступ к

элементам частей массива и к массиву-результату

исключительно последовательный:

индексы-указатели текущего доступа сдвигаются только на

единицу вперед, без возвратов и скачков.

Поэтому операции вида a[i + +] для массива можно заменить

на типовые операции чтения и записи элемента файла с

продвижением к позиции следующего элемента.

При разделении массива нам не приходилось явно отводить

При разделении массива нам не приходилось явно отводить

память под образуемые части и переписывать в них

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

два указателя.

Однако файл читать можно только по одному указателю,

поэтому разделяемые части придется явно переписывать в

отдельные файлы.

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

физическое разделение.

Для разделения массива пополам мы пользовались знанием

Для разделения массива пополам мы пользовались знанием

его длины.

Для файла число его записей не всегда известно и определение

длины требует дополнительного холостого считывания.

Это препятствие мы устраним так:

поскольку разделяются еще неотсортированные файлы,

разделение можно организовать подобно тому, как сдается

колода карт на двух игроков: элементы разделяемого файла по

мере считывания переписываются в два новых файла поочередно.

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

при этом количество элементов в новых файлах отличается

максимум на единицу, что и требуется.

13 86 71 52 99 21 37 45 66 4 75 80 31

13 86 71 52 99 21 37 45 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)

bool split (FILE *f, FILE *fl, FILE * f2)

bool split (FILE *f, FILE *fl, FILE * f2)

/* Разделение 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) сигнализирует о прекращении разделения */

}

void merge (FILE *fl, FILE *f2, FILE *fr)

/* Слияние 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);

}

}

}

void sort_merge (FILE *f)

void sort_merge (FILE *f)

/* Главная процедура сортировки, входной файл должен быть открыт */

{ /* создание временных файлов для частей */

FILE *fl = tmpfile(),

*f2 = tmpfile();

/* разделение на фазе спуска в рекурсию */

if (split(f, fl, f2)) {

sort_merge(f1);

sort_merge(f2);

}

/* слияние на фазе возврата из рекурсии */

merge(f1, f2, f);

/* закрытие и удаление рабочих файлов */

fclose(f1);

fclose(f2);

}

void main ()

void main ()

{ int key x;

FILE * f = 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

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

при с > 0, N  .

Обоснование.

Для заданной последовательности из N элементов может

быть построено N! перестановок. Алгоритм сортировки,

устанавливающий путем сравнения пар, какая из этих

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

фактически осуществляет спуск по так называемому дереву

решений — двоичному дереву, листьями которого являются

решения, а узлами — условия, позволяющие сузить выбор.

Дерево решений для последовательности а, b, с

Дерево решений для последовательности а, b, с

Для задачи сортировки в дереве решений должно быть N!

Для задачи сортировки в дереве решений должно быть N!

листьев. Значит, высота дерева решений  log2 N.

Из неравенства


Похожие:

Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconЗадача сортировки Програмирование на языке высокого уровня Т. Г. Чурина

Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconПрограммирование на языке высокого уровня Для студентов очно-заочной формы обучения

Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconКафедры вс, к т. н. Поляков Артем Юрьевич Рассматриваемые вопросы Жизненный цикл программы и место отладки в нем
Программирование на языке высокого уровня раздел Отладка компьютерных программ
Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconРазработка приложений на языке F# Андрей Терехов Microsoft Украина Немного истории
Сложность удается частично скрыть с помощью инструментов разработки (пример: языки высокого уровня)
Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconКафедры вс, к т. н. Поляков Артем Юрьевич Рассматриваемые вопросы Синтаксис языка и способы его описания
Программирование на языке высокого уровня раздел Базовые конструкции и типы данных языка Си
Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconОтчет комиссии высокого уровня

Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconНеобходимость достижения учащимися высокого уровня социальной компетентности, обеспечивающего их личностное и профессиональное самоопределение

Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconПоследовательность. Арифметическая прогрессия
Наиболее часто встречаются числовые и функциональные последовательности (т е последовательности, членами которых являются числа или...
Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconРешение для автоматизации управления продажами Основной функционал Клиенты, Поставщики, Контакты, Конкуренты, Партнеры
Библиотека файлов, а так же прикрепление файлов к любым документам и справочникам
Cортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей iconТребование стандарта: Требование стандарта
А 36 заданий (из них 26-базового уровня и 10 повышенного) Часть в 8 заданий повышенного уровня Часть с 6 заданий ( 1-повышенного...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница