Курсовая работа: Анализ алгоритмов нечисленной обработки данных

5 Анализ результата. 19

5.1 Линейный поиск. 19

5.2 Двоичный поиск. 20

5.3 Анализ сортировки деревом. 22

Заключение. 24

Список литературы.. 25

Приложение А.. 26

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

1 Постановка задачи

Необходимо:

1) Создать набор входных данных длиной 16, 128, 512, 1024 элементов для программ поиска и сортировки. Для массива длиной, не превышающей 16 элементов, предусмотреть ввод элементов с клавиатуры, в остальных случаях – генератором случайных чисел.

2) Разработать алгоритм и программу упорядочения методом минимальной по памяти турнирной сортировки.

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

4) Осуществить отладку программы на тестовых примерах.

5) Оценить время сортировки и поиска информации для массивов заданной длины.

Требования к программе:

1) основные алгоритмы оформить в виде подпрограмм;

2) программа должна быть самодокументированной;

Обеспечить формирование массива:

1) путем ввода элементов с клавиатуры при n≤16;

2) с помощью генератора случайных чисел при n>16;

2 Метод решения

2.1 Сортировка двоичным деревом

2.1.1 Организация массива в виде двоичного дерева

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

2.1.2 Простейший способ

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

Первый элемент массива поместим в корень дерева. Со вторым элементом поступают так. Сравнивают значение p2 признака этого элемента со значением p1 признака элемента, помещенного в корень дерева (т.е первого элемента).

Если p2<p1, то к корню пририсовывают дугу, направленную влево, и помещают второй элемент в конце этой дуги. Если же p2≥p1, то делают то же самое, но дугу направляют вправо. В общем случае, когда требуется выбрать место на дереве для i-го элемента массива (к этому моменту дерево уже содержит i- 1 вершину и i-2 дуги), поступают следующим образом. В процессе выбора просматривается некоторый путь по дереву (цепочка смежных неповторяющихся вершин и дуг), выходящий всегда из корня. Чтобы, находясь в некоторой вершине пути, определить, обрывается ли путь в этой вершине, а если нет, то какая вершина следующая, применяется один и тот же прием для каждой вершины, в том числе и для корня. Сравнивается значение pi признака размещаемого элемента со значением pk признака элемента, помещенного в данной вершине. Если pi <pk , то смотрят, исходит ли из этой вершины дуга влево. Если исходит, то вершина в конце этой дуги будет следующей вершиной пути, если нет, то достраивают эту дугу и помещают i-й элемент в ее конце. Если же pi ≥ pk , то все происходит аналогично, но с дугой, направленной вправо. Таким образом, из каждой вершины может исходить самое большее две дуги, как и полагается для двоичного дерева.