Лабораторная работа 1. Методы сортировки. Лабораторная работа 3. Методы поиска подстроки в строке.

Лабораторная работа 1. Методы сортировки.

Задание

Реализовать заданный метод сортировки строк числовой матрицы в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию быстрой сортировки (quicksort). Оценить время работы каждого алгоритма сортировки и сравнить его со временем стандартной функции сортировки, используемой в выбранном языке программирования.

Вариант 2. Сортировка Вставкой

Выводы

В проделанной работы были реализованы алгоритмы быстрой сортировки (quicksort) и сортировки вставками (insertion sort). Оба алгоритма работают достаточно быстро, но скорость сортировки ставками в среднем ниже, чем скорость быстрой сортировки, так как число операций в среднем случае для быстрой сортировки – 0(nln(n)) , а сортировки вставками - 0(n2)

Лабораторная работа 3. Методы поиска подстроки в строке.

Задание

Реализовать заданный метод поиска подстроки в строке в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию добавления строк, ввода подстроки и поиска подстроки. Предусмотреть возможность существования пробела. Ввести опцию чувствительности / нечувствительности к регистру. Оценить время работы каждого алгоритма поиска и сравнить его со временем работы стандартной функции поиска, используемой в выбранном языке программирования.

Четный номер по журналу: Кнута-Морриса-Пратта

Выводы

В данной работе реализован алгоритм Кнута-Морриса-Пратта поиска подстроки в строке. Таблица префиксов вычислена за O(m) сравнений, где m - длина поисковой строки, перед началом поиска. А поскольку строка для поиска пройдена ровно один раз, суммарное время работы алгоритма O(m+n), где n — длина текста .