Пример внешней сортировки прямым слиянием

Естественное слияние

В случае простого слияния не учитывается тот факт, что если данные могут быть уже частично отсортированы. На k-ом проходе длина всех сливаемых серий меньше или равна 2^k без учёта того обстоятельства, что могут быть упорядочены и более длинные серии и их можно было бы сливать. Можно было бы сразу сливать какие-либо серии длиною m и n в одну серию длиною т+п. Метод сортировки, при кото­ром каждый раз сливаются две самые длинные, а не фиксированной длины, упорядоченные последовательности, называется естественным слиянием.

шаг 1	шаг 2

Пример внешней сортировки естественным слиянием

Естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах различается не более чем на единицу, называется сбалансированным, в противном случае - несбалансированным. Чтобы в сбалансирован­ном слиянии серии распределялись корректно, необходимо во время записи очеред­ной серии в файл выполнять проверку, не является ли серия продолжением преды­дущей; если является, тогда записать в этот файл не одну, а две серии подряд.

Условие окончания сортировки простым слиянием: количество серий - одна (на фазе слияния).

Улучшенные методы основаны на базе многопутевого естественного сбалансированного слияния.

Многопутевое слияние — это слияние, когда данные распределяют более чем на 2 вспомогательных файла.

Динамическая память и данные с динамической структурой

Во многих случаях при решении задачи возникает проблема минимизации как размеров самой программы, так и области памяти, необходимой для данных. Для существенного сокращения объёма используемой памяти возможны два пути:

• резервировать память только тогда, когда это необходимо;

• резервировать ровно столько, сколько необходимо.

Ранее были рассмотрены базовые структуры данных: массивы, записи, множества (базовые, т.к. поскольку из них можно образовывать более сложные структуры). Такие переменные называются статическими, т.к. для каждой такой переменной на этапе трансляции отводится строго фиксированное место в памяти и на протяжении работы программы за каждой переменной сохранятся этот участок памяти. Объём памяти для расположения статических переменных относительно небольшой. Поэтому достаточно часто могут возникать проблемы нехватки памяти.

Существует возможность создавать более сложные структуры данных. Для них характерно, что в процессе обработки данных изменяются не только значения переменных, но и сама их структура. Соответственно динамически изменяется и размер памяти, занимаемый такими структурами. Поэтому такие данные получили название данных с динамической структурой.

Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

Динамическая память (Heap-область, куча) — это часть оперативной памяти, которая предоставляется программе во время её работы, за вычетом сегмента данных, стека данных и собственно тела программы.

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

Использование динамических величин предоставляет программисту ряд дополнительных возможностей:

1. подключение динамической памяти позволяет увеличить объем обрабатываемых данных.

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

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

4. Элемент динамической структуры состоит как минимум из двух полей:

• информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура;

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

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

Достоинства связного представления данных — в возможности обеспечения значительной изменчивости структур:

• размер структуры ограничивается только доступным объемом машинной памяти;

• при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;

• большая гибкость структуры.

• вместе с тем связное представление не лишено и недостатков, основные из которых:

• на поля связок расходуется дополнительная память;

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