Практическое задание

Добавить в ранее созданную программу с простейшими методами сортировки подпрограммы, реализующие все три улучшенных метода сортировки массивов.

Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Каждый исходный массив должен обрабатываться всеми программами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.

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

Рекомендации по реализации метода Шелла. Для хранения шагов группировки можно ввести вспомогательный массив. После генерации исходного массива надо организовать цикл, в котором запросить и ввести количество шагов и величины самих шагов. Выполнить сортировку исходного массива для нескольких разных наборов шагов и найти среди этих наборов наилучший по числу выполненных сравнений.

2.5. Контрольные вопросы по теме

1. В чем состоит суть сортировки методом Шелла?

2. За счет чего метод Шелла дает лучшие показатели по сравнению с простейшими методами?

3. Приведите практический пример сортировки массива методом Шелла.

4. Какой фактор оказывает наибольшее влияние на эффективность сортировки методом Шелла?

5. Какие последовательности шагов группировки рекомендуются для практического использования в методе Шелла?

6. Как программно реализуется сортировка методом Шелла?

7. В чем состоит суть метода быстрой сортировки?

8. За счет чего метод быстрой сортировки дает лучшие показатели по сравнению с простейшими методами?

9. Что такое опорный элемент в методе быстрой сортировки и как он используется?

10. Приведите практический пример быстрой сортировки массива.

11. Что можно сказать о применимости метода быстрой сортировки с точки зрения его эффективности?

12. Какой фактор оказывает решающее влияние на эффективность метода быстрой сортировки?

13. Почему выбор серединного элемента в качестве опорного в методе быстрой сортировки может резко ухудшать эффективность метода?

14. Какое правило выбора опорного элемента в методе быстрой сортировки является наилучшим и почему его сложно использовать?

15. Какое простое правило выбора опорного элемента в методе быстрой сортировки рекомендуется использовать на практике?

16. Какие усовершенствования имеет базовый алгоритм метода быстрой сортировки?

17. Почему быстрая сортировка проще всего программно реализуется с помощью рекурсии?

18. Как программно реализуется рекурсивный вариант метода быстрой сортировки?

19. Какие особенности имеет не рекурсивная программная реализация метода быстрой сортировки?

20. В чем состоит суть метода пирамидальной сортировки?

21. Какой набор данных имеет пирамидальную организацию?

22. Чем отличаются друг от друга дерево поиска и пирамидальное дерево?

23. Приведите пример пирамидального дерева с целочисленными ключами.

24. Какие полезные свойства имеет пирамидальное дерево?

25. Какие шаги выполняются при построении пирамидального дерева?

26. Что такое просеивание элемента через пирамиду?

27. Приведите практический пример построения пирамидального дерева.

28. Какие шаги выполняются на втором этапе пирамидальной сортировки?

29. Приведите практический пример реализации второго этапа пирамидальной сортировки.

30. Что можно сказать о трудоемкости метода пирамидальной сортировки?

Тема 3. Специальные методы сортировки