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

Сформулируйте постановку задачи сортировки данных, перечислите практические задачи, в которых возникает необходимость сортировки;

Перечислите требования, предъявляемые к алгоритмам сортировки;

Укажите особенности реализации алгоритмов сортировки одномерных массивов данных;

Кратко опишите алгоритм пузырьковой сортировки, укажите его особенности, достоинства и недостатки;

Кратко опишите алгоритм сортировки вставкой, укажите его особенности, достоинства и недостатки;

Кратко опишите алгоритм блочной сортировки, укажите его особенности, достоинства и недостатки;

5.4. Содержание отчета

Отчет по работе должен содержать: номер работы, ее название, цель (с указанием используемых методов), краткое словесное описание всех пользовательских (внутренних и внешних) функций, текст программы, таблицу и график быстродействия, выводы по работе.

5.5. Варианты индивидуальных заданий

Изучить материал методических указаний к практическому занятию по данной теме. Повторить лекционный материал, связанный с массивами, функциями, передачей параметров в функции.

Написать программу, в которой реализуются различные методы сортировки (для одного и того же массива!).

Сравнить реализованные методы по быстродействию. Провести исследование быстродействия для различного числа элементов в массиве (n=100, 1000, 10000). Результаты исследования отразить в отчете в виде таблицы и графика зависимости (t/n) от n.

Для получения исходного (сортируемого) массива следует использовать генератор случайных чисел (функцию rand() из библиотеки <stdlib.h>).

Каждый из методов сортировки, а также генерацию массива, необходимо реализовать в виде отдельной функции. Глобальных переменных не использовать!

Для оценки быстродействия можно использовать функцию clock() из библиотеки <time.h>, возвращающую число тактов процессора, прошедшее с момента запуска приложения. Возвращаемые значения функции clock() следует присваивать переменной типа unsigned long.

Для получения оценки "отлично" необходимо реализовать все три метода сортировки, рассмотренных на практическом занятии, для оценки "хорошо" – любые два метода, для оценки "удовлетворительно" – один из методов. При этом исследование быстродействия на разных по объему массивах является обязательным.

28