Руководство пользователя

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

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

 

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

Рис. Ошибка! Текст указанного стиля в документе отсутствует..2 - Ввод числа меньшего чем 10000

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

Рис. Ошибка! Текст указанного стиля в документе отсутствует..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 <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <ExtCtrls.hpp>

#include <Time.h>

#include <stdio.h>

//---------------------------------------------------------------------------

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 <vcl.h>

#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>=10000)

{

 

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

Mass1 = new int[Kol];

Mass2 = new int[Kol];

Mass3 = new int[Kol];

 

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

for(i=0;i<Kol;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("Количество элементов не должно быть меньше 10000",

"Повторите ввод", 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<Kol;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<Kol;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<Kol;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]<Mass[j])

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<Kol;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);

}