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

Презентация:

Advertisements

Похожие презентации

Циклические алгоритмы Циклические алгоритмы. Алгоритм называется циклическим, если последовательность шагов алгоритма выполняется многократно.

Advertisements

LOGO Определение машины Тьюринга. Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс Это математический объект, а не физическая.

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

МЕТОДЫ СОРТИРОВКИ. Сортировка - расположение элементов множества в порядке расположения некоторого ключа. ОГРАНИЧЕНИЯ: 1. Рассматриваются внутренние сортировки.

ПРОГРАММИРОВАНИЕ/ ЯЗЫКИ ПРОГРАММИРОВАНИЯ Лекция 7 Алгоритмы внешней сортировки (весенний семестр 2012 г.) Доцент Кафедры вычислительных систем, к.т.н.

Программирование Задания В2, В5. Оператор присваивания в языке программирования Задание В2 – базовый уровень, время – 2 мин.

Базы данных в электронных таблицах. Что называется базой данных? Какие примеры баз данных вы знаете? Какие существуют формы представления баз данных?

Базы данных в электронных таблицах 1. Представление базы данных в виде таблицы и формы.

Алгоритмы Алгоритм Алгоритм – это система последовательных команд понятных исполнителю, описывающая процесс преобразования объекта из начального состояния.

Поиск данных. Постановка задачи поиска данных Первый атрибут: набор данных –совокупность данных, среди которых осуществляется поиск; –Элементы набора.

ОДНОМЕРНЫЕ МАССИВЫ. СПОСОБЫ ЗАДАНИЯ ОДНОМЕРНЫХ МАССИВОВ. Понятие массива.

Алгоритм – это … 1.Организованная последовательность действий 2.Понятное и точное предписание исполнителю совершить последовательность действий, направленных.

Массивы данных Подготовила: Камышная И.Н.. Массивы данных Массив – это упорядоченная по возрастанию индексов (номеров) совокупность данных одного типа,

Информатика Учебник для 6 класса Л. Босова Выполнил: Фролов. А. 231группа.

Алгоритмы Введение в программирование. Алгоритм Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми Появление алгоритмов связывают с зарождением математики.

1 Лекция 5 Абстрактные структуры данных. 2 Таблицы Таблица – это набор элементов, содержащих ключ – отличительный признак для поиска элементов, и тело.

Логическое программировыание Презентация 5 Списки в Прологе.

Алгоритмы Введение в программирование. Алгоритм Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города.

АЛГОРИТМ. ИСПОЛНИТЕЛИ ВОКРУГ НАС. ФОРМЫ ЗАПИСИ АЛГОРИТМОВ.

ПРИНЦИПЫ ФОН НЕЙМАНА Ввод Вывод ПАМЯТЬ ПРОЦЕССОР Состав устройств ЭВМ Данные и программы хранятся в общей памяти ЭВМ Данные и программы хранятся в памяти.

Транксрипт:

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

Внешняя сортировка:прямое слияние Имеется последовательный файл A, состоящий из записей a1, a2,..., an Для сортировки используются два вспомогательных файла B и C (размер каждого из них - n/2). Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A.

Внешняя сортировка:прямое слияние Шаг1. Последовательно читается файл A, и записи a1, a3,..., a(n-1) пишутся в файл B, а записи a2, a4,..., an - в файл C (начальное распределение) Шаг2. Начальное слияние производится над парами (a1, a2), (a3, a4),..., (a(n-1), an), Шаг3. Последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. (пример)пример Шаг4. Слияние В и С образуются и пишутся в файл A упорядоченные четверки записей …

Внешняя сортировка:естественное слияние Серией называется подпоследовательность записей ai, a(i+1),..., aj такая, что ak

Внешняя сортировка:естественное слияние При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C, вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла A. Процесс завершается, когда в файле A остается только одна серия. (демо)(демо)

Сбалансированное многопутевое слияние распределение серий исходного файла по m вспомогательным файлам B1, B2,..., Bm и их слияние в m вспомогательных файлов C1, C2,..., Cm. на следующем шаге производится слияние файлов C1, C2,..., Cm в файлы B1, B2,..., Bm и т.д., пока в B1 или C1 не образуется одна серия (демо)(демо)

Многофазная сортировка Из имеющихся m вспомогательных файлов (m-1) файл служит для ввода сливаемых последовательностей, а один - для вывода образуемых серий. Как только один из файлов ввода становится пустым, его начинают использовать для вывода серий, получаемых при слиянии серий нового набора (m-1) файлов. Таким образом, имеется первый шаг, при котором серии исходного файла распределяются по m-1 вспомогательному файлу, а затем выполняется многопутевое слияние серий из (m-1) файла, пока в одном из них не образуется одна серия.