Методы внешней сортировки данных

Содержание

Введение        4

1 Анализ предметной области        5

1.1 Сортировка данных во внешней памяти        5

1.2 Методы сортировки данных во внешней памяти        5

1.2.1 Основные понятия и сортировка со слиянием        5

1.2.2 Прямое слияние        6

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

1.2.4 Сбалансированное многопутевое слияние        8

1.2.5 Многофазная сортировка        9

1.3 Улучшение эффективности внешней сортировки за счет использования основной памяти        11

1.4 Вывод        12

2 Описание программы        13

2.1 Общая характеристика программы        13

2.2 Структура программы и данных        13

2.3 Интерфейс программы        15

2.4 Тестирование программы        17

2.5 Выводы        21

3 Использование программы        22

3.1 Подготовка к исследованию        22

3.2 Зависимость времени сортировки от количества файлов        22

3.3 Выбранная генерация        23

3.3.1 Случайная генерация        23

3.3.2 Генерация в порядке возрастания        24

3.3.3 Генерация в порядке убывания        24

3.4 Выводы        25

Заключение        26

Список используемых источников        27

Приложение А        28

Приложение Б        29

Введение

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

Объектом исследования в курсовой работе являются методы сортировки данных. Предметом исследования являются методы внешней сортировки данных.

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

Для того, чтобы провести исследование, нужно выполнить следующие задачи:

— проанализировать все методы внешней сортировки и выбрать из них наиболее подходящие для исследования;

— создать программу, которая будет генерировать последовательность, сортировать её и записывать данные в файл;

— провести тестирование программы и сделать выводы по её работе;

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

1 Анализ предметной области

1.1 Сортировка данных во внешней памяти

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

Чаще всего внешняя сортировка применяется в системах управления базами данных при выполнении запросов. Стоит отметить, что производительность СУБД сильно зависит от эффективности применяемых методов.

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

1.2 Методы сортировки данных во внешней памяти

1.2.1 Основные понятия и сортировка со слиянием

Чтобы лучше понимать, о чём будет идти речь, дадим несколько определений.

Серией называют упорядоченную последовательность элементов по ключу. Длиной серии называют количество элементов этой серии. Минимальная длина серии равна единице, то есть серия состоит из одного элемента. Такая серия всегда упорядочена.

Слиянием называют процесс объединение упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данных момент. Распределением называют процесс разделения упорядоченных серий на вспомогательные файлы[1].