МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра Информационных Систем
курсовая работа
по дисциплине «Алгоритмы и Структуры Данных»
Тема: Сортировка и поиск данных
Студент гр. 1323 |
|
Мансуров Я.В. |
Преподаватель |
|
Молдовян Д.Н. |
Санкт-Петербург
2023
ОГЛАВЛЕНИЕ
Введение. Постановка задачи и исходные данные…………………………...3
Спецификация……………………………………………………………….….4
Входные данные………………………………………………………………...4
Выходные данные……………………………………………………………....5
Описание алгоритмов…………………………………………………………..6
Код программы………………………………………………………………….7
Заключение……………………………………………………………………...13
Список использованной литературы………………………………………….14
1. Введение. Постановка задачи и исходные данные
Вариант 9. Сортировка и поиск данных.
Содержательная постановка задачи:
Реализовать алгоритм поиска данных
Для разрабатываемого алгоритма реализовать следующие функции: а) использование алгоритмов сортировок вставками, выбором, обменом
б) поиск по ключу с использованием бинарных деревьев поиска с рандомизацией
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 для идеально сбалансированного дерева