Вопросы и упражнения. 1. Сколько сравнений выполняется при сортировке массива из n элементов по алгоритму пузырька?

1. Сколько сравнений выполняется при сортировке массива из n элементов по алгоритму пузырька?

2. При каком условии алгоритм пузырька может завершить сортировку массива за n –2 прохода? за n –3 прохода? На сколько операций сравнения меньше будет выполнено в этих случаях?

3. Предположим, что в алгоритме вставок значение переменной r сравнивается со значениями элементов массива не в обратном порядке (a_k, a_k–1, a_k–2 …, a₁), а в прямом (a₁, a₂, a₃ …, a_k). Повлияет ли это на правильность и эффективность алгоритма? Какой из двух вариантов больше подходит для сортировки Шелла?

4. Объясните, почему в нерекурсивном варианте QuickSort при занесении в стек более длинных отрезков глубина стека оказывается меньше, чем при занесении более коротких.

5. Объясните, почему в рекурсивном варианте QuickSort глубина используемого стека оказывается значительно больше, чем в нерекурсивном.

6. Запрограммируйте смешанный вариант QuickSort, в котором разделение массива и сортировка меньшего из получившихся отрезков выполняется в цикле, а для сортировки большего отрезка используется рекурсивный вызов (при этом нет необходимости явно использовать переменную-стек).

7. Какая глубина стека может потребоваться для реализации QuickSort, описанной в предыдущем упражнении?

8. Алгоритм сортировки называется устойчивым, если элементы массива, имеющие одно и то же значение ключа, сохраняют после сортировки свое взаимное положение. Какие из рассмотренных в разделе алгоритмов являются устойчивыми?

9. Дан массив чисел A = (10, 50, 30, 32, 11, 40, 20, 5, 16, 37, 12, 1). Выполнить сортировку массива по алгоритму ShellSort, используя значения h = 7, 3, 1. Показать состояние массива после каждого прохода.

10. Дан массив чисел A = (20, 13, 5, 25, 16, 18, 40, 32, 21, 11, 1, 30). Выполнить сортировку массива по алгоритму QuickSort. В качестве разделяющего выбирать первый элемент отрезка. Показать состояние массива после каждой операции разделения.

11. Дан массив чисел A = (35, 8, 24, 12, 42, 15, 31, 40, 14, 50). Выполнить преобразование массива в пирамиду (1-я фаза алгоритма HeapSort) и два первых прохода второй фазы алгоритма. Показать состояние массива после каждой операции просеивания.

Сортировка и поиск с использованием деревьев