Федеральное агентство связи
Ордена Трудового Красного Знамени
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра Математической Кибернетики и Информационных Технологий
Отчёт по курсовой работе
по дисциплине: «СиАОД»
на тему:
«Методы сортировки»
Выполнил: студент 2 курса
группы БСТ-2154
Архангельский Максим Вячеславович
Руководитель:
Кутейников Иван Алексеевич
Москва 2023 г.
ОГЛАВЛЕНИЕ
ЗАДАНИЕ №1 3
ЗАДАНИЕ №2 5
ЗАДАНИЕ №3 6
ВЫВОДЫ 7
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 10
ПРИЛОЖЕНИЕ А Листинг программы задания №1 11
ПРИЛОЖЕНИЕ Б Листинг программы задания №2 13
ПРИЛОЖЕНИЕ В Листинг программы задания №3 16
Задание №1
Цель работы: реализовать заданный метод сортировки числовой матрицы в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию быстрой сортировки (quicksort). Оценить время работы каждого алгоритма сортировки и сравнить его со временем стандартной функции сортировки, используемой в выбранном языке программирования.
Вариант: 2 (сортировка вставкой).
Ход работы
Реализация метода быстрой сортировки на языке программирования «Java»:
public static void quickSort(List<Integer> list, int low, int high) {
if (low < high) {
int pivot = list.get(high);
int i = low - 1;
for (int j = low; j < high; j++) {
if (list.get(j) < pivot) {
i++;
Collections.swap(list, i, j);
}
}
Collections.swap(list, i + 1, high);
int pi = i + 1;
quickSort(list, low, pi - 1);
quickSort(list, pi + 1, high);
}
}
Реализация метода сортировки вставками языке программирования «Java»:
public static void insertionSort(List<Integer> list) {
for (int i = 1; i < list.size(); i++) {
int key = list.get(i);
int j = i - 1;
while (j >= 0 && list.get(j) > key) {
list.set(j + 1, list.get(j));
j--;
}
list.set(j + 1, key);
}
}
На рисунке 1 представлены результаты работы программы для массива размером 100 000 элементов. Во время испытаний использовался одинаковый массив для всех трех методов сортировки.
Рисунок 1 — Результат работы программы для массива размером 100 000 элементов
Лучший результат: быстрая сортировка.
Средний результат: стандартная сортировка.
Худший результат: сортировка вставками.
Задание №2
Цель работы: реализовать заданный метод поиска в соответствии с индивидуальным заданием. Организовать генерацию начального набора случайных данных. Для всех вариантов добавить реализацию добавления, поиска и удаления элементов. Оценить время работы каждого алгоритма поиска и сравнить его со временем работы стандартной функции поиска, используемой в выбранном языке программирования.
Вариант: 2 (бинарное дерево и рехеширование с помощью псевдослучайных чисел).
Ход работы
На рисунке 2 изображены результаты работы программы.
Рисунок 2 — Результаты работы программы
Задание №3
Цель работы: реализовать заданный метод поиска подстроки в строке в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию добавления строк, ввода подстроки и поиска подстроки. Предусмотреть возможность существования пробела. Ввести опцию чувствительности / нечувствительности к регистру. Оценить время работы каждого алгоритма поиска и сравнить его со временем работы стандартной функции поиска, используемой в выбранном языке программирования.
Вариант: 2 (Кнута-Морриса-Пратта).
Ход работы
На рисунке 3 изображены результаты работы программы.
Рисунок 3 — Результаты работы программы
ВЫВОДЫ
Задание №1:
Данным программным кодом реализованы три алгоритма сортировки: быстрая сортировка (QuickSort), сортировка вставками (InesrtionSort) и сортировка из стандартной библиотеки Collections (Collections.sort()). Программа тестирует время выполнения каждого из этих алгоритмов на одних и тех же случайно сгенерированных данных размером N = 100000.
Для каждого алгоритма создаются копии исходного массива данных, которые сортируются каждым алгоритмом в отдельном эксперименте. Программа выполняет пять экспериментов и выводит среднее время выполнения каждого алгоритма для этих экспериментов.
Результаты эксперимента выводятся в табличной форме, где для каждого алгоритма показывается среднее время выполнения за пять экспериментов.
Быстрая сортировка (QuickSort) быстрее, чем сортировка вставками (InesrtionSort) и сортировка из стандартной библиотеки Collections (Collections.sort()) на данных объемом N = 100000;
Сортировка вставками (InesrtionSort) занимает больше времени, чем быстрая сортировка (QuickSort) и сортировка из стандартной библиотеки Collections (Collections.sort()) на данных объемом N = 100000;
Все три алгоритма корректно сортируют данные и могут быть использованы для сортировки массивов данных.
Задание №2:
В ходе выполнения задания был разработан код на языке программирования «Java», реализующий бинарное дерево поиска. Класс BinarySearchTree включает методы для добавления, поиска и удаления элементов. Бинарное дерево поиска является эффективным алгоритмом для поиска, особенно при больших наборах данных.
Программа генерирует начальный набор случайных данных для заполнения бинарного дерева поиска и массива, на которых проводятся тесты поиска и удаления элементов.
Время работы алгоритма бинарного дерева поиска и стандартной функции поиска (бинарного поиска) было оценено и сравнено. Результаты показывают, что время работы алгоритма бинарного дерева поиска может быть сопоставимо с временем работы стандартной функции поиска, в зависимости от структуры исходных данных и их размера. Однако стоит учитывать, что для стандартной функции поиска (бинарного поиска) требуется предварительная сортировка массива, что также занимает время.
Было оценено и сравнено между собой время удаления элементов из бинарного дерева поиска и массива. Удаление элемента из бинарного дерева поиска может быть эффективнее, чем удаление из массива, особенно для больших наборов данных, поскольку не требуется перемещение большого количества элементов.
Исходя из полученных результатов, можно сделать вывод, что использование бинарного дерева поиска может быть предпочтительным в некоторых случаях, особенно при больших наборах данных, и частых операциях поиска и удаления элементов. Однако конкретный выбор структуры данных и алгоритма поиска должен быть сделан на основе требований к производительности и специфики конкретной задачи.
Задание №3:
Данный программный код реализован на языке программирования «C#» и содержит реализацию алгоритма Кнута-Морриса-Пратта для поиска подстроки в строке.
Алгоритм использует таблицу префиксов (prefix table), которая определяет наибольший суффикс подстроки, который является ее префиксом. При каждом сравнении символа в строке с подстрокой, алгоритм использует эту таблицу для определения наибольшего смещения.
Помимо этого, код содержит обработчик события кнопки «button1_Click», который получает исходную строку и подстроку из текстовых полей «textBox1» и «textBox2», выполняет поиск подстроки в строке с помощью метода «KMPSearch» и выводит результат в метку «label1». Кроме того, код выводит время работы алгоритма в миллисекундах в метку «label2».
Особенности данной программы:
Алгоритм Кнута-Морриса-Пратта позволяет быстро и эффективно искать подстроки в строках;
При необходимости алгоритм может быть модифицирован для учета регистра символов или для работы с Unicode.
Данный код реализует алгоритм и предоставляет пользовательский интерфейс для ввода исходной строки и подстроки, а также для отображения результатов и времени выполнения;
Использование таблицы префиксов значительно ускоряет поиск, так как позволяет пропускать большое количество символов при несовпадении символов в строке и подстроке;