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

Реализовать программу, объединяющую простейшие методы сортировки массивов:

· сортировку обменом (метод пузырька)

· сортировку выбором

· сортировку вставками

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

Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку “на месте”, т.е. изменяет исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как параметр-значение.

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

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

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

1. В чем состоит задача выбора алгоритмов решения однотипных задач?

2. Какие критерии используются при выборе алгоритмов?

3. Как оценивается трудоемкость алгоритма?

4. Что такое О-нотация и для чего она используется?

5. Какие группы функций можно выделить с помощью О-нотации?

6. Какие рекомендации следует использовать при выборе алгоритмов с помощью О-нотации?

7. Что можно сказать о применимости алгоритмов класса О(2ⁿ) и О(n!)?

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

9. Как классифицируются методы сортировки?

10. Что такое внутренняя и внешняя сортировка и в чем состоят особенности этих задач?

11. В чем состоят особенности универсальных и специальных методов внутренней сортировки?

12. Какие основные методы сортировки относятся к универсальным и какую они имеют трудоемкость?

13. В чем состоит практическое значение изучения простейших методов сортировки?

14. Как классифицируются методы поиска?

15. В чем состоит суть метода сортировки обменом?

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

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

18. В чем достоинства и недостатки метода сортировки обменом?

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

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

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

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

23. В чем достоинства и недостатки метода сортировки вставками?

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

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

26. Какие шаги выполняет алгоритм сортировки выбором?

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

28. В чем достоинства и недостатки метода сортировки выбором?

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