1. Сортировка обменом Пояснения:

1. def bubble_sort(arr):: Определяет функцию bubble_sort, которая принимает список arr в качестве аргумента. Список передается по ссылке, то есть функция изменяет исходный список.
2. """...""": Документирующая строка (docstring), описывающая функцию.
3. n = len(arr): Получаем длину списка arr.
4. for i in range(n - 1):: Внешний цикл. Проходит по списку n-1 раз. После каждой итерации (прохода по списку) самый большой элемент "всплывает" в конец неотсортированной части.
5. swapped = False: Флаг, который показывает, были ли обмены элементами во внутреннем цикле. Используется для оптимизации: если за проход не было ни одного обмена, значит список уже отсортирован.
6. for j in range(n - i - 1):: Внутренний цикл. Сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке. n - i - 1 используется для того, чтобы не проверять уже отсортированные элементы в конце списка (после каждого прохода внешнего цикла один элемент оказывается на своем месте).
7. if arr[j] > arr[j + 1]:: Если текущий элемент больше следующего, меняем их местами.
8. arr[j], arr[j + 1] = arr[j + 1], arr[j]: Меняем местами элементы arr[j] и arr[j + 1] с помощью множественного присваивания в Python.
9. swapped = True: Устанавливаем флаг swapped в True, чтобы отметить, что был обмен.
10. if not swapped:: Если swapped остался False после внутреннего цикла, значит, не было ни одного обмена, а это означает, что список уже отсортирован.
11. break: Выходим из внешнего цикла, так как список отсортирован.
12. if name == "main":: Запускает код только тогда, когда скрипт запускается напрямую.
13. my_list = [5, 1, 4, 2, 8]: Создаем список для сортировки.
14. print("Исходный список:", my_list): Выводим исходный список.
15. bubble_sort(my_list): Вызываем функцию сортировки.
16. print("Отсортированный список:", my_list): Выводим отсортированный список.

Как работает скрипт:

Сортировка обменом (пузырьковая сортировка) - это простой алгоритм сортировки. Он работает, многократно проходя по списку, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Большие элементы "всплывают" в конец списка, как пузырьки в воде. Проходы по списку повторяются до тех пор, пока список не будет отсортирован.

Временная сложность:

• Лучший случай: O(n) - Когда список уже отсортирован. В этом случае внутренний цикл выполняется один раз, но без обменов, и алгоритм завершается благодаря проверке if not swapped. • Средний случай: O(n^2) • Худший случай: O(n^2) - Когда список отсортирован в обратном порядке. 2) Сортировка слиянием Как работает скрипт:

1. merge_sort(arr): • Проверяет базовый случай: если длина массива меньше или равна 1, он уже отсортирован, и функция возвращает его. • Находит середину массива и разделяет его на две половины: left и right. • Рекурсивно вызывает merge_sort для каждой половины, чтобы отсортировать их. • Вызывает функцию merge(left, right) для слияния двух отсортированных половин в один отсортированный массив.

2. merge(left, right): • Создает пустой список result для хранения отсортированного результата. • Использует два указателя (i и j) для итерации по left и right соответственно. • Сравнивает элементы left[i] и right[j] и добавляет наименьший из них в result. Увеличивает соответствующий указатель (i или j). • После того, как один из списков (left или right) закончился, добавляет все оставшиеся элементы из другого списка в result. • Возвращает отсортированный список result.

3. main.py: • Импортирует функцию merge_sort из файла merge_sort.py. • Создает пример массива arr. • Вызывает merge_sort для сортировки массива. • Выводит исходный и отсортированный массивы.

Временная сложность:

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

• O(log n) представляет собой количество уровней рекурсии (разбиений) в алгоритме. • O(n) представляет собой время, необходимое для слияния двух отсортированных половин на каждом уровне рекурсии.

Пространственная сложность:

Сортировка слиянием требует дополнительной памяти для хранения временных массивов, создаваемых при слиянии. Таким образом, пространственная сложность составляет O(n). Это считается недостатком сортировки слиянием по сравнению с некоторыми алгоритмами сортировки на месте (например, быстрая сортировка), которые требуют меньше дополнительной памяти (хотя быстрая сортировка в худшем случае также может потребовать O(n) дополнительной памяти из-за рекурсии). 3) Быстрая сортировка Как работает скрипт:

1. quick_sort(arr): (Версия с созданием нового списка) • Выбирает опорный элемент (pivot). В данном примере это середина списка. • Создает три списка: less (элементы меньше pivot), equal (элементы равны pivot), greater (элементы больше pivot). • Рекурсивно вызывает quick_sort для less и greater и объединяет результаты с equal.

2. quick_sort_in_place(arr, low, high): (Версия "на месте") • Рекурсивно сортирует подмассив arr[low...high]. • Вызывает функцию partition для разбиения подмассива. • Рекурсивно сортирует левую и правую части относительно pivot.

3. partition(arr, low, high): • Выбирает последний элемент (arr[high]) в качестве pivot. • Перемещает все элементы, меньшие или равные pivot, в левую часть подмассива. • Возвращает индекс pivot после разбиения.

4. main.py: • Демонстрирует использование обеих версий quick_sort. • Показывает, что версия quick_sort создает новый отсортированный список, не изменяя исходный. • Показывает, что версия quick_sort_in_place сортирует список "на месте", изменяя исходный список.

Временная сложность:

• Лучший и средний случай: O(n log n). Это происходит, когда опорный элемент (pivot) выбирается хорошо и разбивает список на примерно равные части. • Худший случай: O(n^2). Это происходит, когда опорный элемент каждый раз является наименьшим или наибольшим элементом списка. В этом случае рекурсия выполняется n раз, и каждая итерация занимает O(n) времени. Худший случай часто возникает, когда список уже отсортирован или почти отсортирован, и опорный элемент всегда выбирается как первый или последний элемент. Для избежания худшего случая рекомендуется выбирать опорный элемент случайным образом или использовать медиану трех элементов.

Пространственная сложность:

• Версия quick_sort(arr) (с созданием новых списков): O(n) - требуется дополнительная память для создания новых списков less, equal и greater. Хотя теоретически рекурсия может достигать глубины log n, в худшем случае, когда разделение неравномерное, может потребоваться O(n) дополнительной памяти. • Версия quick_sort_in_place(arr, low, high) (на месте): O(log n) - это связано с рекурсивным вызовом функций, который требует место в стеке вызовов. В лучшем и среднем случаях глубина рекурсии составляет log n, а в худшем - n. В среднем случае пространственная сложность считается O(log n). В худшем случае (например, когда массив уже отсортирован и pivot выбирается неудачно) пространственная сложность может достигать O(n). Сортировка обменом неэффективна для больших списков. Она чаще используется в учебных целях или для небольших наборов данных.

Пространственная сложность: O(1) - Сортировка выполняется на месте (in-place). 4) Последовательный поиск Как работает скрипт:

1. sequential_search(arr, target): • Перебирает элементы списка arr один за другим, начиная с первого элемента. • Для каждого элемента сравнивает его со значением target. • Если элемент равен target, функция немедленно возвращает индекс этого элемента. • Если функция доходит до конца списка, не найдя target, она возвращает -1.

2. Пример использования: • Создает пример списка my_list и значение target_value. • Вызывает функцию sequential_search для поиска target_value в my_list. • Выводит сообщение, указывающее, был ли найден target_value и, если да, то по какому индексу.

Временная сложность:

Последовательный поиск имеет следующую временную сложность:

• Лучший случай: O(1). Это происходит, когда искомый элемент target находится в самом начале списка. Функция сразу же возвращает его индекс. • Средний случай: O(n/2), что упрощается до O(n). В среднем, нужно просмотреть половину списка, чтобы найти элемент. • Худший случай: O(n). Это происходит, когда искомый элемент target находится в конце списка или вообще отсутствует в списке. В этом случае необходимо просмотреть все n элементов списка.

Таким образом, в общем случае временная сложность последовательного поиска составляет O(n). Это означает, что время выполнения алгоритма растет линейно с увеличением размера списка. Последовательный поиск прост в реализации, но неэффективен для больших списков. Для больших наборов данных рекомендуется использовать более эффективные алгоритмы поиска, такие как бинарный поиск (если список отсортирован). 5) Интерполирующий поиск Как работает скрипт:

1. interpolation_search(arr, target): • Инициализирует переменные low и high для обозначения границ поиска в списке. • Выполняет цикл while до тех пор, пока low не станет больше high или пока target не выйдет за пределы значений arr[low] и arr[high]. Это условие важно, чтобы избежать ошибок деления на ноль и других проблем, если target находится вне диапазона списка. • Вычисляет предполагаемую позицию pos элемента target с помощью формулы интерполяции. Формула предполагает, что значения в списке распределены более или менее равномерно. • Если arr[pos] равен target, функция возвращает pos. • Если arr[pos] меньше target, функция обновляет low, чтобы продолжить поиск в правой части списка. • Если arr[pos] больше target, функция обновляет high, чтобы продолжить поиск в левой части списка. • Если цикл завершается без нахождения target, функция возвращает -1.

2. Пример использования: • Создает отсортированный список my_list и значение target_value. • Вызывает функцию interpolation_search для поиска target_value в my_list. • Выводит сообщение, указывающее, был ли найден target_value и, если да, то по какому индексу.

Временная сложность:

Временная сложность интерполирующего поиска зависит от распределения значений в списке:

• Лучший случай: O(log log n). Это происходит, когда значения в списке распределены равномерно. В этом случае интерполирующий поиск очень быстро сужает область поиска. • Средний случай: В среднем случае, при равномерном распределении, временная сложность близка к O(log log n). • Худший случай: O(n). Это происходит, когда значения в списке распределены неравномерно, особенно когда значения сгруппированы в определенных областях. В этом случае интерполирующий поиск может выродиться в последовательный поиск. Например, если список содержит много одинаковых значений или значения увеличиваются экспоненциально.

Таким образом, в то время как в лучшем и среднем случаях интерполирующий поиск может быть значительно быстрее, чем бинарный поиск (O(log n)), он очень чувствителен к распределению данных. Если вы не уверены, что данные распределены равномерно, безопаснее использовать бинарный поиск.