Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задание на лабораторную работуСтр 1 из 2Следующая ⇒
Алгоритмы внутренней сортировки
Методические указания к лабораторной работе по дисциплине «Методы программирования»
Самара 2008 УДК 004.424.5
Составитель: к.т.н., доцент Журавлев Д.Ю
Методические указания к лабораторной работе по дисциплине «Методы программирования»
Самарский государственный аэрокосмический университет имени академика С.П. Королева, Самара, 2008 г. – 20 с.
Содержатся рекомендации и пояснения к выполнению лабораторной работы по исследованию свойств различных методов внутренней сортировки линейных структур данных. Методические указания разработаны на кафедре компьютерных систем СГАУ и предназначены для студентов очной формы обучения по специальности 075500 «Комплексное обеспечение информационной безопасности автоматизированных систем»
ВВЕДЕНИЕ Целью лабораторной работы является знакомство с основными алгоритмами внутренней сортировки линейных массивов данных. Лабораторная работа предусматривает реализацию основных алгоритмов внутренней сортировки на языке программирования C\C++, а также проведение экспериментального сравнения показателей временной сложности алгоритмов и проведение качественного анализа их свойств. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
В рамках лабораторной работы необходимо:
1. Разработать программу, реализующую три алгоритма внутренней сортировки линейного массива на языке программирования C\C++: · Простая обменная сортировка (метод «пузырька») · Сортировка методом Шелла · Быстрая сортировка Хоара
Длина сортируемого массива задается пользователем во время работы программы, т.е. память под массив должна выделяться динамически, а элементы массива должны заполняться случайными числами.
В коде программы для каждого реализуемого метода сортировки необходимо предусмотреть переменные-счетчики, для определения числа операций попарных сравнений и перестановок элементов, совершенных в ходе выполнения операций сортировки. Результирующие значения счетчиков необходимо выводить на экран после каждого выполнения операции сортировки.
2. Провести экспериментальное исследование зависимости числа сравнений и перестановок от длины сортируемого массива для каждого метода.
На основании серии экспериментов построить таблицы и графики искомых зависимостей и качественно определить их характер – линейный, логарифмический, экспоненциальный, и т.д. Сравнить экспериментальные результаты с теоретическими оценками временной сложности исследуемых методов внутренней сортировки.
|