Физическое проектирование программного обеспечения

Таблица 2

Имя модуля Заголовок Функции Формальные параметры Выполняемое действие
MainUnit.cpp SimpleChoose *mass , int Kol Сортировка Массива mass с количеством элементов Kol методом простого выбора.
MainUnit.cpp InsertionSort *mass , int Kol Сортировка Массива mass с количеством элементов Kol методом простых вставок.
MainUnit.cpp CountCompares *mass , int Kol Сортировка Массива mass с количеством элементов Kol методом подсчета сравнений.
MainUnit.cpp TForm1::Btn_SortClick - Выделение памяти под массивы с количеством элементов, полученных из формы, заполнение массива случайными числами; вызываем методы сортировки, выводим сообщение о завершении операции.
MainUnit.cpp TForm1::DrawGis - Построение гистограммы на основе данных в переменных InsertionSort, CountCompares, SimpleChoose

Проектирование интерфейса

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

В качестве форм ввода-вывода информации на экран будут использованы следующие компоненты:

· TEdit (для ввода количества элементов )

· TButton ( «Сортировать», «показать время работы алгоритмов»

· TLabel (для статических надписей на формах )

· TImage (для прорисовки гистограммы)

Все эти компоненты есть в стандартном наборе компонентов C++ Builder, они просты в использовании как для написания программы, так и для ее использования.

7. Кодирование

Реализация алгоритма сортировки методом простого выбора.

Листинг 1.1

// Выполняем сортировку

for(i=Kol-1;i>0;i--)

{

//Устанавливаем начальное значение и номер

//для максимального элемента

Max = Mass[i];

n =i;

// Ищем максимальный элемент

for(j=0;j<=i-1;j++)

{

if (Mass[j]> Max)

{

Max= Mass[j];

Mass[j]= Mass[n];

Mass[n]=Max;

}

}

Реализация алгоритма сортировки методом простых вставок.

Листинг 1.2

// Выполняем сортировку

for(i=0;i<Kol;i++)

{

Tmp=Mass[i];

for(j=i-1;j>=0 && Mass[j]>Tmp;j--)

Mass[j+1] = Mass[j];

Mass[j+1] = Tmp;

}

Реализация алгоритма сортировки методом подсчета сравнений.

Листинг 1.3


// Производим сортировку

for (i =1; i <= Kol ; i ++)

c[i]=0;

for (i=Kol; i>=2;i--)

for(j=i-1; j>=1; j--)

if (Mass[i]<Mass[j])

c[j]++;

else

c[ i ]++;

for (i =1; i <= Kol ; i ++)

b[c[i]] = Mass[i];

8. Тестирование.

Таблица 3

Исходные данные Тестируемый модуль или подпрограмма Ожидаемый результат
1000 элементов массива TForm1::SimpleChoose Сохранение массива, отсортированного методом простого выбора в файл и подсчет времени выполнения
1000 элементов массива TForm1::InsertionSort Сохранение массива, отсортированного методом простых вставок в файл и подсчет времени выполнения
1000 элементов массива TForm1::CountCompares Сохранение массива, отсортированного методом подсчета сравнений в файл и подсчет времени выполнения
1000 элементов массива TForm1::DrawGis Построение гистограммы по значениям времени работы.
10000 элементов MainUnit.cpp Подсчет времени работы каждого метода сортировки и построение гистограммы.

Таблица 4

Дата, время Тестируемый модуль или подпрограмма Кто проводил тестирование Описание теста Результаты тестирования
10.12.14 TForm1::SimpleChoose Кузнецов Р.А. Проверка работы сортировки массива из 1000 элементов методом простого выбора Успех
10.12.14 TForm1::InsertionSort Кузнецов Р.А. Проверка работы сортировки массива из 1000 элементов методом простых вставок Успех
10.12.14 TForm1::CountCompares Кузнецов Р.А. Проверка работы сортировки массива из 1000 элементов методом подсчета сравнений Успех
13.12.14 MainUnit.cpp Кузнецов Р.А. Проверка работы подсчета времени работы алгоритмов сортировки массива из 10000 элементов Ошибка. Неверный отсчет времени
13.12.14 MainUnit.cpp Кузнецов Р.А. Проверка работы подсчета времени работы алгоритмов сортировки массива более 20000 элементов Вылет программы
13.12.14 MainUnit.cpp Кузнецов Р.А. Проверка работы подсчета времени работы алгоритмов сортировки массива более 20000 элементов Успех

Заключение

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

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

Список литературы

1. Н. Вирт. Алгоритмы и структуры данных. — СПб.: Невский диалект, 2008.

2. https://ru.wikipedia.org/

3. http://kvodo.ru/

4. "Программирование и основы алгоритмизации" - В.Г. Давыдов - изд. "Высшая школа", 2005

5. "Программирование на языке высокого уровня" - Т.А. Павловская - изд. "Питер", 2004.

Приложения

Приложение 1

Техническое задание

Введение

Наименование программы

Наименование программы: «Сортировка данных»

Наши рекомендации