1. Вопросы и упражнения

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) и два первых прохода второй фазы алгоритма. Показать состояние массива после каждой операции просеивания.

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

   1. Задача поиска со вставкой

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

В качестве примера можно рассмотреть информационную подсистему по контингенту студентов. Запросы типа «найти такого-то студента» могут перемежаться корректировками контингента: одного студента отчислить, другого зачислить в порядке перевода из другого вуза, у такой-то студентки изменить фамилию.

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

Как организовать эффективный поиск в подобной ситуации? Конечно, можно при каждой корректировке массива предпринимать действия для сохранения его сортированности. Но это потребует времени порядка O(n)на каждую корректировку. Например, при вставке нового элемента потребуется сначала определить, на какое место он должен быть вставлен (это бинарный поиск, т.е.O(log(n))), а потом сдвинуть последующие элементы на одну позицию, чтобы освободить выбранное место. В среднем придется сдвигать половину элементов массива, что и дает оценкуO(n).

А если не заботиться о сохранении сортированности? Тогда корректировки могут быть выполнены очень быстро, за время порядка O(1)(например, можно вставлять новые элементы всегда в конец массива), но поиск при этом замедляется доO(n)(линейный, а не бинарный поиск).

Возможно ли такое решение проблемы, чтобы оценка времени как для поиска, так и для вставки/удаления элементов не превышала «хорошего» O(log(n))? Да, возможно, но для этого придется отказаться от использования такой структуры данных, как массив, и воспользоваться более гибкими сцепленными структурами.

В связи с вышесказанным, в данном разделе мы будем рассматривать не чистую задачу поиска, а задачу поиска со вставкой, которую можно сформулировать следующим образом. Дана таблицаA, представленная некоторой структурой данных. Дано также значение ключаx. Требуется проверить наличие в таблице записи с данным ключом, в случае отсутствия такой записи вставить ее в таблицу и в любом случае предоставить доступ к найденной или вставленной записи.

Обратная операция, а именно удаление записи с заданным ключом, не будет подробно рассматриваться в данном пособии. Как правило, если известно, как добавляется новая запись, то нетрудно понять и как она должна удаляться. В некоторых случаях будут отмечены особенности операции удаления записей.

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