Список заданий по ДМ-сем2

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 2 семестр

1. Постройте массив, в котором сортировка выбором делает максимальное число обменов
2. Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
3. Найдите минимальное число сравнений для сортировки 4 элементов
4. Найдите минимальное число сравнений для сортировки 5 элементов
5. Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
6. Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
7. Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
8. Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
9. Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
10. Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$

</wikitex>