Алгоритмы внутренней сортировки
Методические указания к лабораторной работе по дисциплине
«Методы программирования»
Самара 2008
УДК 004.424.5
Составитель: к.т.н., доцент Журавлев Д.Ю
Методические указания к лабораторной работе по дисциплине
«Методы программирования»
Самарский государственный аэрокосмический университет имени академика С.П. Королева, Самара, 2008 г. – 20 с.
Содержатся рекомендации и пояснения к выполнению лабораторной работы по исследованию свойств различных методов внутренней сортировки линейных структур данных.
Методические указания разработаны на кафедре компьютерных систем СГАУ и предназначены для формы обучения по специальности 075500 «Комплексное обеспечение информационной безопасности автоматизированных систем»
 |
ВВЕДЕНИЕ
Целью лабораторной работы является знакомство с основными алгоритмами внутренней сортировки линейных массивов данных. Лабораторная работа предусматривает реализацию основных алгоритмов внутренней сортировки на языке программирования C\C++, а также проведение экспериментального сравнения показателей временной сложности алгоритмов и проведение качественного анализа их свойств.
ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
В рамках лабораторной работы необходимо:
1. Разработать программу, реализующую три алгоритма внутренней сортировки линейного массива на языке программирования C\C++:
- Простая обменная сортировка (метод «пузырька»)
- Сортировка методом Шелла
- Быстрая сортировка Хоара
Длина сортируемого массива задается пользователем во время работы программы, т.е. память под массив должна выделяться динамически, а элементы массива должны заполняться случайными числами.
В коде программы для каждого реализуемого метода сортировки необходимо предусмотреть переменные-счетчики, для определения числа операций попарных сравнений и перестановок элементов, совершенных в ходе выполнения операций сортировки. Результирующие значения счетчиков необходимо выводить на экран после каждого выполнения операции сортировки.
2. Провести экспериментальное исследование зависимости числа сравнений и перестановок от длины сортируемого массива для каждого метода.
На основании серии экспериментов построить таблицы и графики искомых зависимостей и качественно определить их характер – линейный, логарифмический, экспоненциальный, и т.д. Сравнить экспериментальные результаты с теоретическими оценками временной сложности исследуемых методов внутренней сортировки.
РЕКОМЕНДАЦИИ К РАЗРАБОТКЕ КОМПЬЮТЕРНОЙ ПРОГРАММЫ
Разрабатываемая компьютерная программа должна обладать интуитивным пользовательским интерфейсом, который позволяет в диалоговом режиме изменять основные параметры программы, а также предоставляет средства управления ее работой.
Основой пользовательского интерфейса программы является главное меню.
Рисунок 1. Пример структуры главного меню программы
Динамическое выделение памяти под массив заданной длины
Разрабатываемая программа должна позволять пользователю задавать произвольную длину сортируемого массива. Следовательно, выделение памяти под сортируемый массив должно происходить динамически.
По окончанию операции сортировки выделенная память освобождается, т.к. в дальнейшем практическое использование отсортированных данных не предусмотрено.
Пример фрагмента программы, выделяющей память под массив заданной длины и заполняющей его случайными значениями, а затем освобождающей выделенную память:
#include
#include
#include
…
// Указатель на массив данных
int * intVector = NULL;
// Переменная длины массива
int n = 20;
…
// Функция выделения памяти под массив
// и заполнения его случайными значениями
int * AllocateArray(int length)
{
int * vec = new int[length];
if (vec)
{
srand (time(NULL));
for (int i=0; i
}
return vec;
}
// Функция освобождения памяти, выделенной под массив
void ReleaseArray(int ** vec)
{
if (*vec) delete (*vec)[];
*vec=NULL;
}
…
…
// Инициализация массива
intVector = AllocateArray(n);
…
// Манипуляции с массивом (например, сортировка)
…
// Освобождение массива
ReleaseArray(intVector);
…
Алгоритмы сортировки
Простая обменная сортировка (метод «пузырька»)
Сортировка включениями с уменьшающимися расстояниям (метод Шелла)
Быстрая сортировка с разделением (метод Хоара)
