Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

 

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

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

 

 

Самара 2008


УДК 004.424.5

 

 

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

 

 

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

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

 

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

 

 

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

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

 

 
 

ВВЕДЕНИЕ


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

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

 

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

 

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

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

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

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

 

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

 

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

 

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

 

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

 

 







© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.