Заключение. 
Сортировка методом перестановки данных

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

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

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

• 1. Н. Вирт. Алгоритмы и структуры данных. — СПб.: Невский диалект, 2008.
• 2. https://ru.wikipedia.org/
• 3. http://kvodo.ru/
• 4. «Программирование и основы алгоритмизации» В. Г. Давыдов изд. «Высшая школа», 2005
• 5. «Программирование на языке высокого уровня» Т. А. Павловская изд. «Питер», 2004.

Приложения

Приложение 1.

• 1. Техническое задание
• 1. Введение
• 1.1. Наименование программы

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

1.2. Назначение и область применения Программа создана для сравнения по скорости работы 3-х способов сортировки данных в одномерном динамическом массиве: простого выбора, простых вставок, подсчета сравнений.

• 2. Требования к программе
• 2.1. Требования к функциональным характеристикам

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

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

• 3. Условия эксплуатации
• 3.1. Климатические условия эксплуатации

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

3.2. Требования к составу и параметрам технических средств В состав технических средств должен входить IВМ-совместимый персональный компьютер (ПЭВМ), процессор Pentium-2.0Hz, оперативную память объемом не менее 512 мб, операционную систему Цindows xp.

3.3. Требования к информационной и программной совместимости Среда Borland C++ Builder 6.

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

5. Технико-экономические показатели Экономическая эффективность не рассчитывается.

• 6. Стадии и этапы разработки
• 6.1. Стадии и этапы разработки.

Таблица 5.

6.2. Порядок контроля и приемки Таблица 6.

Приложение 2.

Алгоритм метода простых вставок.

Алгоритм метода простого выбора.

Приложение 3.

Руководство пользователя Внешний вид программы представлен на Рис. 1.

Рис. 1.

Пользователь вводит в поле «Количество элементов» размер массива и нажимает кнопку «Сортировать». По-умолчанию в этом поле стоит число 10 000, т.к. это условие задания. Если мы вводим число меньше 10 000, то получаем сообщение о неправильности ввода Рис 2.

Рис. 2.

Если мы вводим в поле «Количество элементов» символы не являюшиеся числами или вещественное число, то у нас выйдет следующее сообщение:

Рис. 3.

Если же мы ввели корректное число то программа выдаст сообщение что сортировка завершена (Рис. 4).

Рис. 4.

После нажатия кнопки «OK» отобразится гистограмма (Рис. 5).

Рис. 5.

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

Кроме того программа записывает 3 тестовых файла. Алгоритм простого выбора создает файл «SimpleChoose.txt». Внешний вид файла приведен на Рис. 6.

Рис. 6.

Алгоритм сортировки вставками создает файл «InsertionSort» (Рис.7).

Рис. 7.

Алгоритм подсчета сравнений создает файл «CountCompares» (Рис. 8).

Рис. 8.

Приложение 4.

Листнинг Модуль MainUnit.h.

//—————————————————————————————————————;

#ifndef MainUnitH.

#define MainUnitH.

//—————————————————————————————————————;

#include.

#include.

#include.

#include.

#include.

#include.

#include.

//—————————————————————————————————————;

class TForm1: public TForm.

{.

__published: // IDE-managed Components.

TImage *Img_Gis;

TLabel *L_KolEl;

TEdit *Ed_KolEl;

TButton *Btn_Sort;

TLabel *Label1;

void __fastcall Btn_SortClick (TObject *Sender);

private: // User declarations.

// Очищает поле и рисует оси.

void DrawField (void);

// Метод простого выбора.

int SimpleChoose (int *Mass, int Kol);

// Метод простых вставок.

int InsertionSort (int *Mass, int Kol);

// Метод подсчета сравнений.

int CountCompares (int *Mass, int Kol);

// Изображение гистограммы.

void DrawGis (int first, int second, int third);

public: // User declarations.

__fastcall TForm1(TComponent* Owner);

};

//—————————————————————————————————————;

extern PACKAGE TForm1 *Form1;

//—————————————————————————————————————;

#endif.

Модуль MainUnit.cpp.

//—————————————————————————————————————;

#include.

#pragma hdrstop.

#include «MainUnit.h» .

//—————————————————————————————————————;

#pragma package (smart_init).

#pragma resource «*.dfm» .

TForm1 *Form1;

//—————————————————————————————————————;

__fastcall TForm1: TForm1(TComponent* Owner).

: TForm (Owner).

{.

this->DrawField ();

}.

//—————————————————————————————————————;

void TForm1: DrawField (void).

{.

int xo, yo; // Начало координат.

// Устанавливаем начало координат.

xo = 20;

yo = Img_Gis->Height 20;

// Очищаем поле.

this->Img_Gis->Canvas->Brush->Color = clWhite;

this->Img_Gis->Canvas->FloodFill (10,10,clYellow, fsBorder);

// Рисуем оси.

this->Img_Gis->Canvas->MoveTo (xo, yo);

this->Img_Gis->Canvas->LineTo (xo, 20);

this->Img_Gis->Canvas->MoveTo (xo, yo);

this->Img_Gis->Canvas->LineTo (Img_Gis->Width 20, yo);

}.

//—————————————————————————————————————;

void __fastcall TForm1: Btn_SortClick (TObject *Sender).

{.

long i, Kol; // Индекс и количество элементов массива.

int *Mass1, *Mass2, *Mass3, // Указатели на массивы.

// Время работы алгоритмов.

simplechoose, // Простого выбора.

insertionsort, // Простых вставок.

countcompares; // Подсчет сравнений.

// Включаем генератор случайных чисел.

randomize ();

try.

{.

// Считываем количество элементов с формы.

Kol = StrToInt (Ed_KolEl->Text);

if (Kol>=10 000).

{.

// Создаем динамические массивы.

Mass1 = new int[Kol];

Mass2 = new int[Kol];

Mass3 = new int[Kol];

// Заполняем массивы случайными числами.

for (i=0;i.

{.

Mass1[i] = random (Kol*2);

Mass2[i] = Mass1[i];

Mass3[i] = Mass1[i];

}.

// Вызываем методы сортировки.

simplechoose = SimpleChoose (Mass1,Kol);

insertionsort = InsertionSort (Mass2,Kol);

countcompares = CountCompares (Mass3,Kol);

// Выводим сообщение о конце операции.

Application->MessageBox («Сортировка завершена» ," Сообщение", MB_OK);

// Рисуем гистограмму.

DrawGis (simplechoose, insertionsort, countcompares);

}.

else.

Application->MessageBox («Количество элементов не должно быть меньше 10 000» ,.

" Повторите ввод", MB_OK);

}.

catch (EConvertError&).

{.

Application->MessageBox («Вы ввели ошибочное число» ,.

" Повторите ввод", MB_OK);

}.

}.

//—————————————————————————————————————;

// Метод простого выбора.

int TForm1: SimpleChoose (int *Mass, int Kol).

{.

FILE *f;

int start, end, vremya, // Начало и конец отсчета.

i, j, // Индексы.

Max, n; // Максимальный элемент и его номер

// Начинаем отсчет времени.

start = clock ();

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

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;

}.

}.

}.

// Заканциваем отсчет времени.

end = clock ();

vremya = end start;

// Записываем осортированный массив в файл.

f = fopen («SimpleChoose.txt» ," w");

for (i=0;i.

fprintf (f," %d", Mass[i]);

// Закрываем файл.

fclose (f);

return vremya;

}.

//—————————————————————————————————————;

// Метод простых вставок.

int TForm1: InsertionSort (int *Mass, int Kol).

{.

FILE *f;

int start, end, vremya, // Начало и конец отсчета.

i, j, k, // Индексы.

Tmp; // Буфер

// Начинаем отсчет времени.

start = clock ();

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

for (i=0;i.

{.

Tmp=Mass[i];

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

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

Mass[j+1] = Tmp;

}.

// Заканциваем отсчет времени.

end = clock ();

vremya = end start;

// Записываем осортированный массив в файл.

f = fopen («InsertionSort.txt» ," w");

for (i=0;i.

fprintf (f," %d", Mass[i]);

// Закрываем файл.

fclose (f);

return vremya;

}.

//—————————————————————————————————————;

// Метод подсчета сравнений.

int TForm1: CountCompares (int *Mass, int Kol).

{.

FILE *f;

int start, end, vremya, // Начало и конец отсчета.

i, j, k, // Индексы.

*b, *c; // Вспомогательные массивы.

// Создаем вспомогательные массивы.

b = new int[Kol];

c= new int[Kol];

// Начинаем отсчет времени.

start = clock ();

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

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].

c[j]++;

else.

c[ i ]++;

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

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

// Заканциваем отсчет времени.

end = clock ();

vremya = end start;

// Записываем осортированный массив в файл.

f = fopen («CountCompares.txt» ," w");

for (i=0;i.

fprintf (f," %d", b[i]);

// Закрываем файл.

fclose (f);

return vremya;

}.

//—————————————————————————————————————;

// Изображение гистограммы.

void TForm1: DrawGis (int first, int second, int third).

{.

int Max; // Максимальное время.

float del, // Точек на деление.

xo, yo, // Начало координат.

w, h; // Ширина и высота столбца.

char str[10]; // Время в милисекундах.

Max = first;

if (second > Max).

Max = second;

if (third > Max).

Max = third;

del = (float)(Img_Gis->Height-40)/Max;

// Очищаем поле.

DrawField ();

// Устанавливаем начало координат.

xo = 20;

yo = Img_Gis->Height 20;

w = (Img_Gis->Width 40)/3;

// Рисуем гистограммы.

// Метод простого выбора.

if (first≠0).

h = (int)first*del;

else.

h=0;

Img_Gis->Canvas->Rectangle (xo, yo, xo+w, yo-h);

this->Img_Gis->Canvas->Brush->Color = clRed;

this->Img_Gis->Canvas->FloodFill (xo+w/2,yo-h/2,clBlack, fsBorder);

itoa (first, str, 10);

this->Img_Gis->Canvas->Brush->Color = clWhite;

this->Img_Gis->Canvas->TextOut (xo+10,yo-h-15,str);

// Метод простых вставок.

if (second≠0).

h = (int)second*del;

else.

h=0;

Img_Gis->Canvas->Rectangle (xo+w, yo, xo+2*w, yo-h);

this->Img_Gis->Canvas->Brush->Color = clGreen;

this->Img_Gis->Canvas->FloodFill (xo+w+w/2,yo-h/2,clBlack, fsBorder);

itoa (second, str, 10);

this->Img_Gis->Canvas->Brush->Color = clWhite;

this->Img_Gis->Canvas->TextOut (xo+w+10,yo-h-15,str);

// Метод подсчета сравнений.

if (third≠0).

h = third*del;

else.

h=0;

Img_Gis->Canvas->Rectangle (xo+2*w, yo, xo+3*w, yo-h);

this->Img_Gis->Canvas->Brush->Color = clBlue;

this->Img_Gis->Canvas->FloodFill (xo+2*w+w/2,yo-h/2,clBlack, fsBorder);

itoa (third, str, 10);

this->Img_Gis->Canvas->Brush->Color = clWhite;

this->Img_Gis->Canvas->TextOut (xo+2*w+10,yo-h-15,str);

}.