МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра Информационных Систем

курсовая работа

по дисциплине «Алгоритмы и Структуры Данных»

Тема: Сортировка и поиск данных

Студент гр. 1323		Мансуров Я.В.
Преподаватель		Молдовян Д.Н.

Санкт-Петербург

2023

ОГЛАВЛЕНИЕ

1. Введение. Постановка задачи и исходные данные…………………………...3

2. Спецификация……………………………………………………………….….4

3. Входные данные………………………………………………………………...4

4. Выходные данные……………………………………………………………....5

5. Описание алгоритмов…………………………………………………………..6

6. Код программы………………………………………………………………….7

7. Заключение……………………………………………………………………...13

8. Список использованной литературы………………………………………….14

1. Введение. Постановка задачи и исходные данные

Вариант 9. Сортировка и поиск данных.

Содержательная постановка задачи:

1. Реализовать алгоритм поиска данных

2. Для разрабатываемого алгоритма реализовать следующие функции: а) использование алгоритмов сортировок вставками, выбором, обменом

б) поиск по ключу с использованием бинарных деревьев поиска с рандомизацией

3. Программа должна быть написана в соответствии со стандартом

Формальная постановка задачи:

• созданном файле имеются cведения о газетах (название газеты, индекс издания, фамилию, ФИО редактора, цену экземпляра газеты).

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

Исходные данные:

Сведения о газетах (название газеты, индекс издания, фамилию, ФИО редактора, цену экземпляра газеты).

Ограничения на исходные данные:

Нет

2. Спецификация

№	Входные данные (формальное	Результат (Выходные
спецификации	описание)	данные)
1.	Запуск без отладки	Меню выбора действий
2.	Функции работы с базой данных
2.1	Открыть файл	Данные считываются с файла
2.2	Вывод данных	Доступ к выходным данным
3.	Функции из задания курсовой работы
3.1	Сортировка данных (по названию газеты)	Сортировка данных
3.1.0	Без ввода данных вручную или открытия файла	Данные отсутствуют

3. Входные данные

Paper D

24680

Alex

9

Paper B

67890

Petta

12

Paper A

12345

Ivan

10

Paper C

54321

Elena

8

Paper G

13579

Olga

11

Ограничения на входные данные:

Нет

4. Выходные данные

Отсортированные данные по названию газеты:

5. Описание алгоритмов

Пузырьковая сортировка или Bubble Sort

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

Сортировка вставками или Insertion Sort

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

Сортировка выбором или Selection Sort

• Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.

	Выбором	Вставками	Пузырьковая
Худшее время	O(n^2)	O(n^2)	O(n^2)
Лучшее время	O(n^2)	O(n)	O(n)
Среднее время	O(n^2)	O(n^2)	O(n^2)
Затраты памяти	O(n)	O(n)	O(1)

Бинарное рандомизированное дерево

• это алгоритм, в котором каждый узел двоичного дерева поиска будет содержать ключ key, который, по сути, управляет всеми процессами, и пару указателей left и right на левое и правое поддеревья. Если какой-либо указатель нулевой, то соответствующее этому указателю дерево является пустым. Помимо этого, нам для реализации рандомизированного дерева потребуется еще одно поле size, в котором будет храниться размер дерева с корнем в данном узле.

Основное свойство дерева поиска — любой ключ в левом поддереве меньше корневого ключа, а в правом поддереве — больше корневого ключа, то есть ключи дерева отсортированы . Это свойство позволяет нам очень просто организовать поиск заданного ключа, перемещаясь от корня вправо или влево в зависимости от значения корневого ключа.

Идея рандомизации заключается в том, что, если ключи как следует перемешать, то получится создать неплохо сбалансированное дерево – его высота будет порядка 2log2n против log2n для идеально сбалансированного дерева