Ниже приведен график зависимости времени поиска от количества элементов массива.
Рисунок 2. График результатов двоичного поиска
Вывод: Из рисунка 2 видно, что график двоичного поиска имеет логарифмический характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения двоичного поиска.
Данный метод удобен для массивов с большой длиной, но его использование возможно только в упорядоченных массивах.
5.3 Анализ сортировки деревом
Анализ сортировки деревом был проведен на примере массива длиной в 16, 128, 512, 1024 элементов.
Результаты представлены в виде нижеследующей таблицы.
Таблица 6. Результаты сортировки
Количество элементов в массиве
16
128
512
1024
Количество перестановок
18
130
514
1026
Ниже приведен график сортировки деревом.
Рисунок 3. График сортировки деревом.
Вывод: Организация массива в виде двоичного дерева требует несколько больших затрат как на организацию массива, так и на поиск в нем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение не столь существенно. Этот метод оптимален по порядку роста трудоемкости поиска в зависимости от размера массива.
Сортировка деревом не является минимальной по памяти, так как на построения дерева необходимы большие затраты памяти, но процесс сортировки с помощью данного метода занимает мало времени.
Заключение
В процессе выполнения данного курсового проекта изучены и разработаны алгоритмы нечисленной обработки данных: линейный и двоичный поиск заданного элемента, а также упорядочение массива методом сортировки дерева. Был проведен анализ результатов программы, который подтвердил правильность составления и отладки программы. Для наглядности результатов работы программы построены графики и составлены таблицы.
Список литературы
1. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983г.
2. Лавров С.С, Гончаров Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971г.
3. Попов В.Б. Turbo Pascal. М.: Финансы и статистика, 2007г.
Приложение А
Таблицы идентификаторов
Таблица А.1: Идентификаторы основной программы
Имя параметра
Физический смысл параметра
Тип параметра
n
Длина исходного массива до 1024 элементов
integer
i
Счетчик, индекс элемента массива
j
Счетчик, индекс элемента массива, указатель
x
Искомое число
a
Одномерный числовой массив (исходный массив)
mas=array [1..1024] of integer
b
Двумерный числовой массив, дерево, образованное из исходного массива
mas2=array [1..1024, 1..5] of integer
b1
Двумерный числовой массив, сортируемое дерево
F
Текстовый файл для хранения исходного массива
text
F_1
Текстовый файл для хранения отсортированного массива, сортируемого массива после каждой перестановки
Таблица А.2: Идентификаторы процедуры VVod
Счетчик, индекс элемента формируемого массива
Длина формируемого массива
Формируемый массив
Таблица А.3: Идентификаторы процедуры Vivod
Счетчик, индекс элемента выводимого на экран массива
Длин массива, выводимого на экран
Выводимый на экран массив
Таблица А.4: Идентификаторы процедуры Save_To_File
i1
Счетчик, индекс элемента массива, сохраняемого в файл
Файл, в который необходимо записывать сортируемый массив после каждой перестановки
Длина массива
Исходный массив, сохраняемый в файл
m
А.5 Идентификаторы процедуры Lin_Poisk
k
Количество сравнений
Массив, в котором необходимо найти искомый элемент
Искомый элемент
Таблица А.6 Идентификаторы процедуры Dv_Poisk
sri
Индекс среднего элемента в массиве
vi
Индекс верхнего элемента в массиве
ni
Индекс нижнего элемента в массиве
f
Флаг нахождения искомого элемента в массиве
boolean
Страницы: 1, 2, 3, 4, 5
