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

Разработать программу в виде программного комплекса, включающего в себя модули (функции):

• модули сортировки;

• модуль формирования массива;

• печать массива;

• модуль замера времени;

• программу, реализующую диалог с пользователем.

Разрабатываемый программный комплекс должен обеспечивать

• вывод на экран меню;

• ввод исходной информации;

• формирования массивов с большим числом элементов;

• выбор метода сортировки;

• сортировку массива;

• печать результата;

• замеры времени выполнения сортировок массива.

Программа должна обеспечить сортировку массивов размером произвольной длины до 1000 элементов и выводить для контроля:

- при небольшом количестве элементов (например, менее 25) - неупорядоченный массив и массив после сортировки для каждого из предложенных алгоритмов;

- при значительном объеме данных (более 25) выводить время сортировки одного и того же массива для всех четырех предложенных алгоритмов.

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

В модуле сортировки реализуются:

• метод сортировки выбором;

• метод сортировки пузырьком;

• метод сортировки включением;

• метод сортировки слиянием.

• метод быстрой сортировки

Демонстрация работоспособности разработанных программных средств должна обеспечивать два варианта контроля: контроль работоспособности каждого из методов и контроль временных характеристик всех реализованных методов. Эффективность различных алгоритмов сортировки массивов, состоящих из n сортируемых элементов проводиться по двум критериям: числу необходимых сравнений элементов С и числу перестановок элементов М. Для всех прямых методов сортировки можно дать точные аналитические формулы. Они приведены в таблице 20.1.

Таблица 19.1

Сравнение прямых методов сортировки

Метод	Минимальное		Среднее		Максимальное
Прямое включение	С = M =	n – 1 2(n – 1)		(n2 + n – 2) / 4 (n2 – 9n – 10) / 4		(n2 – n) / 2 – 1 (n2 – 3n – 4) / 2
Прямой выбор	С = M =	(n2 – n) / 2 3(n – 1)		(n2 – n) / 2 n * (ln n + 0.57)		(n2 – n) / 2 n2 / 4 + 3(n – 1)
Прямой обмен	С = M =	(n2 – n) / 2 0		(n2 – n) / 2 (n2 – n) * 0.75		(n2 – n) / 2 (n2 – n) * 1.5

Заключение

Несмотря на появление все новых и новых языков программирования, Си остается по-прежнему широко распространен и востребован. Только язык Си позволяет быстро создавать компиляторы для новых платформ, драйверы устройств. Максимальная приближенность Си к архитектуре вычислительной машины позволяет писать на нем быстрые и эффективные программы. А современные тенденции к повсеместному использованию микроконтроллеров делают его незаменимым при создании управляющих программ. Поэтому владение языком Си важно для большинства специалистов в сфере информационных технологий и вычислительной техники.

Язык Си служит базовой платформой для изучения объектно-ориентированных языков С++, Java, C#. Он также относится к классу универсальных языков и с его помощью можно решить широкий круг прикладных задач. Полученные навыки программирования на Си обеспечат легких переход к другим языкам высокого уровня и явятся достаточным инструментом для решения большинства профессиональных задач.

Данное пособие предназначено для изучения языка Си, как первого языка программирования. Она охватывает такие «классические» принципы программирования, как линейные и разветвленные алгоритмы, организацию циклов и многовариантного управления процессом обработки, включает рассмотрение стандартных типов данных, массив, структур, работы со стандартными и файловыми потоками. В пособии представлено множество примеров кода для анализа, практических заданий и задач различного уровня сложности. Такой практикориентированный подход к изложению материала должен способствовать формированию необходимых для будущего ИТ-специалиста навыков программирования.