Динамическое выделение памяти под массив заданной длины

Методы внутренней сортировки

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

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

Самара 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);

Методы сортировки

Обычная обменная Динамическое выделение памяти под массив заданной длины сортировка (способ «пузырька»)

Сортировка включениями с уменьшающимися расстояниям (способ Шелла)

Стремительная сортировка с разделением (способ Хоара)


dihaniya-i-zreniya-v-neprigodnoj-dlya-dihaniya-srede.html
dihatelnaya-gimnastika-dlya-ukrepleniya-immuniteta.html
dihatelnaya-meditativnaya-gimnastika.html