Задание на лабораторную работу

Алгоритмы внутренней сортировки

Методические указания к лабораторной работе по дисциплине

«Методы программирования»

Самара 2008

УДК 004.424.5

Составитель: к.т.н., доцент Журавлев Д.Ю

Методические указания к лабораторной работе по дисциплине

«Методы программирования»

Самарский государственный аэрокосмический университет имени академика С.П. Королева, Самара, 2008 г. – 20 с.

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

Методические указания разработаны на кафедре компьютерных систем СГАУ и предназначены для студентов очной формы обучения по специальности 075500 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Целью лабораторной работы является знакомство с основными алгоритмами внутренней сортировки линейных массивов данных. Лабораторная работа предусматривает реализацию основных алгоритмов внутренней сортировки на языке программирования C\C++, а также проведение экспериментального сравнения показателей временной сложности алгоритмов и проведение качественного анализа их свойств.

ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

В рамках лабораторной работы необходимо:

1. Разработать программу, реализующую три алгоритма внутренней сортировки линейного массива на языке программирования C\C++:

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

· Сортировка методом Шелла

· Быстрая сортировка Хоара

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

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

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

На основании серии экспериментов построить таблицы и графики искомых зависимостей и качественно определить их характер – линейный, логарифмический, экспоненциальный, и т.д. Сравнить экспериментальные результаты с теоретическими оценками временной сложности исследуемых методов внутренней сортировки.