Практикум по программированию

1.Даны два списка a и b упорядоченных по неубыванию. Объедините их в один упорядоченный по неубыванию список. Сложность алгоритма при этом должна обязательно быть меньше квадратичной.

Решение оформите в виде функции, возвращающей новый список без модификации исходных списков merge(a: list, b: list) -> list.

2.Даны два списка чисел, упорядоченных по возрастанию (каждый список состоит из различных элементов). Найдите пересечение данных множеств, т.е. те числа, которые входят в оба массива. Алгоритм должен иметь сложность O(n+m). То есть, количество операций алгоритма должно быть не больше, чем заранее известная константа, умноженная на (n+m) .

Решение оформите в виде функции intersection(a: list, b: list) -> list, возвращающий пересечение двух данных списков. Полученный список должен быть упорядочен по возрастанию.

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

Каждый проход по списку надо осуществлять в обратном порядке – от последнего элемента к первому. К элементам списка обращайтесь по индексу. Итератор обхода списка не использовать.

4.Реализуйте функцию сортировки (по возрастанию) для списка методом квадратичного выбора.

Предполагается, что количество элементов в списке является квадратом целого числа.

Алгоритм квадратичного выбора:

1. Создаем пустой список для отсортированных элементов.
2. Разделяем список на √n групп по √n элементов и находим минимальный элемент в каждой подгруппе. 
3. Выбираем минимальный элемент из минимальных элементов подгрупп и помещаем его в конец списка для отсортированных элементов (из подгруппы удаляем).
4. Выбираем минимальный элемент из оставшихся элементов подгруппы, из которой удалили минимальный элемент на предыдущем шаге.
5. Возвращаемся к пункту 3.

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

Если количество элементов в списке, являющемся параметром функции, не равно квадрату целого числа, то функция должна генерировать исключение.

КАЖДУЮ ЗАДАЧУ ОТДЕЛЬНЫМ ФАЙЛОМ

Python