5.2.3.Модуль Unit2.Cpp (для Формы GrafForm)

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

Информация отображается в двух видах – в виде графика зависимости времени и размерности для каждого метода сортировки, и в виде прямолинейных диаграмм по каждой размерности для каждого метода сортировки. Вывод статистики меняется в зависимости от выбора способа заполнения исходных массивов (радио-кнопкой – переключателем).

Для реализации этого модуля предусмотрены глобальные массивы:

• short arSize[4] = {5,7,9,25} – массив для хранения размерностей массивов.

• TColor arColors[4] = {clRed, clBlue, clFuchsia, clLime} – массив для хранения значений цвета для каждого метода сортировки.

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

При наступлении события от переключателя (смена способа заполнения исх.массива) функция обработки этого события вызывает Основную функцию с соответствующим параметром.

Также в модуле есть вспомогательная функция округления вещественного числа до указанного кол-ва цифр десятичной части.

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

6.Листинг программы

6.1.Файл Unit1.h

Этот заголовочный файл автоматически создается средой разработки Borland Builder, однако в него были внесены изменения (описание глобального массива структур для хранения статистики), поэтому представление его листинга имеет смысл. Этот листинг уже был представлен в разделе 5.2.1. Напомню, что этот код вписывается в раздел объявления глобальных переменных – public.

6.2.Файл Unit2.h

Этот заголовочный файл автоматически создается средой разработки Borland Builder. Т.к. в него изменения не вносились, нет смысла представлять его листинг.

6.3.Файл Unit1.cpp

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

#include <vcl.h>

#include <dos.h>

#pragma hdrstop

#include "Unit1.h"

#include "Unit2.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

// массив для определения размерностей массивов

short arSizes[4] = {5,7,9,25};

// максимальная размерность

const MaxSize = 25;

// текущая размерность

short CurSize;

//исходный массив

//первая размерность - для убывающей и случайного порядков заполнения

//вторая размерность - для каждого размера

//[MaxSize] - кол-во элементов

short arSource[2][4][MaxSize];

// массив с результатом сортировки

//первая размерность - для убывающей и случайного порядков заполнения

//[MaxSize] - кол-во элементов

short arRes[2][MaxSize];

// кол-во повторений сортировок

unsigned int SortCount;

// время копирования из массива в массив с кол-вом сортировок SortCount раз

double t_copy;

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

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

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

// вывод на экран исх.массивов

void PutSourceAr()

{

short i; // счетчик для цикла

Form1->lboxUSource->Items->Clear(); // очищаем старое содержимое убывающего массива

Form1->lboxRSource->Items->Clear(); // очищаем старое содержимое массива со случ.значениями

for (i = 0; i < arSizes[CurSize]; i++){ // цикл заполнения ListBox'ов новыми значениями массивов

Form1->lboxUSource->Items->Strings[i] = arSource[0][CurSize][i]; // массив с убывающ.значениями

Form1->lboxRSource->Items->Strings[i] = arSource[1][CurSize][i]; // массив со случ.значениями

}

}

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

// заполнение исх.массива случ. значениями

void GetRandAr()

{

short i; // счетчик для цикла

for (i = 0; i < arSizes[CurSize]; i++) // цикл заполнения массива случ.значениями

arSource[1][CurSize][i] = Random(100);

}

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

// определение времени копирования из одного массива

// в другой с кол-вом копирований SortCount раз

void GetTcopy()

{

unsigned int j; // счетчик цикла повторений копирования SortCount раз

short i; // счетчик цикла копирования элементов массива

struct time c1,c2; // переменные для фиксирования времени

short B[MaxSize]; // массив, в котором будем выполнять копирование

gettime(&c1); // фиксируем начальное время

for (j = 0; j < SortCount; j++) // цикл повторений копирования SortCount раз

for (i = 0; i < MaxSize; i++) // цикл копирования элементов массива

B[i] = arSource[0][3][i]; // копируем элементы из одного массива в другой

gettime(&c2); // фиксируем конечное время

// переводим показания зафиксированного времени в секунды и считаем разницу между конечным и начальным временем в секундах

t_copy = ((c2.ti_hour*360000.+c2.ti_min*6000.+ c2.ti_sec*100.+c2.ti_hund)-(c1.ti_hour*360000.+ c1.ti_min*6000.+c1.ti_sec*100.+c1.ti_hund))/100.;

}

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

// установка начальных значений массивов

// установка загаловков таблицы статистики

void __fastcall TForm1::FormActivate(TObject *Sender)

{

short i,j; // счетчики циклов

// установка названий методов сортировки в созданной структуре Methods[4]

// глобальная структура Methods описана в заголовочном файле Unit1.h

// структура Methods объявлена глобальной для обращения к ней из другой формы проекта (вывод графика)

Form1->Methods[0].Name = "Отбором";

Form1->Methods[1].Name = "Вставки";

Form1->Methods[2].Name = "Пузырек";

Form1->Methods[3].Name = "Быстрая";

SortCount = StrToInt(edCount->Text); // присваиваем значение кол-ва повторений сортировок

t_copy = -1.00; // значение времени копирования из одного массива в другой пока не определено, поэтому ставим отриц.значение

//заполняем исх.массивы значениями (убывающ. и случайны порядки)

for (i = 3; i >= 0; i--) { // пробегаем циклом по всем размерностям (5,7,9,25 эл.)

CurSize = i; // запоминаем текущую размерность в глобальную переменную

GetRandAr(); // заполняем массив текущей размерности случайными значениями

for (j = 0; j < arSizes[CurSize]; j++) // цикл заполнения массива текущей размерности значениями в убывающ.порядке

arSource[0][CurSize][j] = arSizes[CurSize]-j;

}

PutSourceAr(); // выводим на экран в ListBox'ы заполненыые массивы (случайный и убывающ. порядки)

// выводим на экран массив в случайном порядке для задачи ПОИСКА

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

Form1->lboxFindSource->Items->Strings[i] = arSource[1][3][i];

//заполняем заголовки таблицы статистики (StringGrid1)

for (i = 0; i < 4; i++){

StringGrid1->Cells[i*2+2][0] = "Убыв.";

StringGrid1->Cells[i*2+3][0] = "Случ.";

StringGrid1->Cells[0][i*4+1] = IntToStr(arSizes[i]) + " эл.";

StringGrid1->Cells[1][i*4+1] = "Срав-я";

StringGrid1->Cells[1][i*4+2] = "Присв-я";

StringGrid1->Cells[1][i*4+3] = "Эф-ность";

StringGrid1->Cells[1][i*4+4] = "Время";

}

}

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

// очистка результата сортировки

void ClearSorted()

{

Form1->lboxUSorted->Items->Clear();

Form1->lboxRSorted->Items->Clear();

Form1->lbMethod->Caption = "";

Form1->lbSize->Caption = "";

Form1->lbUCompare->Caption = "";

Form1->lbRCompare->Caption = "";

Form1->lbUChange->Caption = "";

Form1->lbRChange->Caption = "";

Form1->lbUEffect->Caption = "";

Form1->lbREffect->Caption = "";

Form1->lbUTime->Caption = "";

Form1->lbRTime->Caption = "";

}

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

// вывод результата сортировки, заполнение таблицы статистики

// параметры: Method - метод сортировки, который будем выводить на экран

// Compares[] - массив с двумя элементами со значениями кол-ва сравнений для убыв. и случ. порядков

// Changes[] - массив с двумя элементами со значениями кол-ва присваиваний для убыв. и случ. порядков

// Eff[] - массив с двумя элементами со значениями еффективности для убыв. и случ. порядков

// Tsort[] - массив с двумя элементами со значениями времени выполнения для убыв. и случ. порядков

void PutResAr(short Method, unsigned int Compares[], unsigned int Changes[], int Eff[], double Tsort[])

{

short i; // счетчик цикла

ClearSorted(); // очистка результата предыдущей сортировки

// заполняем структуру Methods значениями

for (i = 0; i <= 1; i++) { // цикл по порядкам заполнения (убыв. и случ.)

Form1->Methods[Method].Compares[i][CurSize] = Compares[i];

Form1->Methods[Method].Changes[i][CurSize] = Changes[i];

Form1->Methods[Method].Eff[i][CurSize] = Eff[i];

Form1->Methods[Method].Tsort[i][CurSize] = Tsort[i];

}

// выводим на экран в ListBox'ы массивы с результатом сортировки

for (i = 0; i < arSizes[CurSize]; i++){ // цикл по всем элементам текущей размерности

Form1->lboxUSorted->Items->Strings[i] = arRes[0][i]; // результат сортировки с убыв.порядком

Form1->lboxRSorted->Items->Strings[i] = arRes[1][i]; // результат сортировки со случ.порядком

}

// выводим инфо на экран в раздел РЕЗУЛЬТАТ СОРТИРОВКИ

Form1->lbMethod->Caption = Form1->Methods[Method].Name;

Form1->lbSize->Caption = arSizes[CurSize];

Form1->lbUCompare->Caption = Form1->Methods[Method].Compares[0][CurSize];

Form1->lbRCompare->Caption = Form1->Methods[Method].Compares[1][CurSize];

Form1->lbUChange->Caption = Form1->Methods[Method].Changes[0][CurSize];

Form1->lbRChange->Caption = Form1->Methods[Method].Changes[1][CurSize];

Form1->lbUEffect->Caption = FloatToStr(Form1->Methods[Method].Eff[0][CurSize]);

Form1->lbREffect->Caption = FloatToStr(Form1->Methods[Method].Eff[1][CurSize]);

Form1->lbUTime->Caption = Form1->Methods[Method].Tsort[0][CurSize];

Form1->lbRTime->Caption = Form1->Methods[Method].Tsort[1][CurSize];

// заполняем таблицу статистики StringGrid1

Form1->StringGrid1->Cells[Method*2+2][CurSize*4+1]=Compares[0];

Form1->StringGrid1->Cells[Method*2+3][CurSize*4+1]=Compares[1];

Form1->StringGrid1->Cells[Method*2+2][CurSize*4+2]=Changes[0];

Form1->StringGrid1->Cells[Method*2+3][CurSize*4+2]=Changes[1];

Form1->StringGrid1->Cells[Method*2+2][CurSize*4+3]=Eff[0];

Form1->StringGrid1->Cells[Method*2+3][CurSize*4+3]=Eff[1];

Form1->StringGrid1->Cells[Method*2+2][CurSize*4+4]=Tsort[0];

Form1->StringGrid1->Cells[Method*2+3][CurSize*4+4]=Tsort[1];

}

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

// обработка кнопки "Другие случайные значения"

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

// обнуление статистики выполнения для старых значений

void __fastcall TForm1::btRandomClick(TObject *Sender)

{

short i,j,k; // счетчики циклов

GetRandAr(); // заполняем массив текущей размерности случайными значениями

PutSourceAr(); // выводим на экран в ListBox'ы заполненыые массивы (случайный и убывающ. порядки)

ClearSorted(); // очищаем результат предыдущей сортировки

Form1->btGraf->Enabled = false; // делаем недоступной кнопку вывода графика, т.к. новые значения еще не отсортированы

for (i = 0; i < 4 ; i++){ // цикл обнуления статистики для старых значений текущей размерности

for (k = 1; k <= 4; k++) { // обнуляем статистику в StringGrid1 для текущей размерности

Form1->StringGrid1->Cells[i*2+3][CurSize*4+k] = "";

}

for (j = 0; j <= 1; j++) { // обнуляем статистику в структуре Methods для текущей размерности

Methods[i].Compares[j][CurSize] = 0;

Methods[i].Changes[j][CurSize] = 0;

Methods[i].Eff[j][CurSize] = 0;

Methods[i].Tsort[j][CurSize] = 0.0;

}

}

}

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

// обработка события переключения на размерность 5 эл.

void __fastcall TForm1::RadioButton1Click(TObject *Sender)

{

CurSize = 0; // устанавливаем глобальную переменную текущей размерности в значение 0 = 5 эл.

PutSourceAr(); // выводим на экран в ListBox'ы значения массивов новой выбранной размерности

ClearSorted(); // очищаем результат предыдущей сортировки

}

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

// обработка события переключения на размерность 7 эл.

void __fastcall TForm1::RadioButton2Click(TObject *Sender)

{

CurSize = 1; // устанавливаем глобальную переменную текущей размерности в значение 1 = 7 эл.

PutSourceAr(); // выводим на экран в ListBox'ы значения массивов новой выбранной размерности

ClearSorted(); // очищаем результат предыдущей сортировки

}

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

// обработка события переключения на размерность 9 эл.

void __fastcall TForm1::RadioButton3Click(TObject *Sender)

{

CurSize = 2; // устанавливаем глобальную переменную текущей размерности в значение 2 = 9 эл.

PutSourceAr(); // выводим на экран в ListBox'ы значения массивов новой выбранной размерности

ClearSorted(); // очищаем результат предыдущей сортировки

}

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

// обработка события переключения на размерность 25 эл.

void __fastcall TForm1::RadioButton4Click(TObject *Sender)

{

CurSize = 3; // устанавливаем глобальную переменную текущей размерности в значение 3 = 25 эл.

PutSourceAr(); // выводим на экран в ListBox'ы значения массивов новой выбранной размерности

ClearSorted(); // очищаем результат предыдущей сортировки

}

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

// очистка таблицы статистики

void ClearStat()

{

short i,j,k; // счетчики циклов

// обнуляем всю структуру Methods

for (i = 0; i < 4; i++) // цикл размерностей массивов

for (j = 0; j < 4; j++) { // цикл методов сортировки

for (k = 0; k <= 1; k++) { // цикл порядков значений массивов (убыв. и случайный)

Form1->Methods[j].Compares[k][i] = 0;

Form1->Methods[j].Changes[k][i] = 0;

Form1->Methods[j].Eff[k][i] = 0;

Form1->Methods[j].Tsort[k][i] = 0.0;

}

}

// обнуляем всю статистику в StringGrid1

for (i = 2; i <= 10; i++) // цикл столбцов

for (j = 1; j <= 17; j++) // цикл строк

Form1->StringGrid1->Cells[i][j] = "";

Form1->btGraf->Enabled = false; // делаем недоступной кнопку вывода графика, т.к. статистика пуста

}

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

// изменение кол-ва сортировок пользователем

void __fastcall TForm1::edCountChange(TObject *Sender)

{

SortCount = StrToInt(edCount->Text); // присваиваем новое значение кол-ва повторений сортировок SortCount

ClearStat(); // обнуляем всю старую статистику

GetTcopy(); // получаем новое время копирования из массива в массив с новым кол-вом повторений

}

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

// функция сортировки методом Отбора с кол-вом повторений сортировок SortCount раз

// параметры: arA[] - исх.массив, arRes[] - массив с результатом

// arSize - кол-во эл. массива,

// Compares - возвращает кол-во операций сравнения

// Changes - возвращает кол-во операций присваивания

// Eff - эффективность алгоритма = (Compares + Changes*10)

// T_sort - время в секундах, затраченное на сортировку

void MSelect(short arA[], short arRes[], int arSize, unsigned int& Compares, unsigned int& Changes, int& Eff, double& T_sort)

{

struct time t1,t2; // переменные для замера времени выполнения сортировки

int i,j,k,x;

unsigned int c;

Compares = 0;

Changes = 0;

if (t_copy == -1.00)

GetTcopy(); // замеряем время копирования из одного массива в другой, если оно не было замерено ранее

// производим сортировку один раз для подсчета кол-ва Сравнений и Присваиваний

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

arRes[i] = arA[i]; // скопируем содержимое исх.массива в массив с результатом

Compares++; // увеличим счетчик сравнений перед сравнением условия выхода из цикла в след.цикле

Changes++; //увеличим счетчик присваиваний перед предстоящим присваиванием начального значения для счетчика цикла

for (i = 0; i < arSizes[CurSize]; i++) { //цикл перебора всех элементов массива

k = i; // запоминаем текущий индекс

x = arRes[i]; // запоминаем текущий элемент массива

Changes+= 2; //изменим кол-во присваиваний, т.к. в предыдущ.2-х строчках делали присваивания

Compares++; // увеличим счетчик сравнений перед сравнением условия выхода из цикла в след.цикле

Changes++; //увеличим счетчик присваиваний перед предстоящим присваиванием начального значения для счетчика цикла

for ( j = i + 1; j < arSizes[CurSize]; j++) { // цикл выбора наименьшего элемента, проходим от i+1 до конца массива

Compares++; //увеличиваем счетчик сравнений перед предстоящим сравнением

if (arRes[j] < x ) {

k = j; // k - индекс меньшего элемента, чем x

x = arRes[j]; // запоминаем меньший элемент

Changes+= 2; // увеличиваем счетчик присваиваний после двух присваиваний

}

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций j

}

arRes[k] = arRes[i]; // меняем местами наименьший с arRes[i]

arRes[i] = x;

Changes+= 2; // увеличиваем счетчик присваиваний после двух присваиваний

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций i

}

// сортировка закончена

// сортировка SortCount раз с фиксированием времени выполнения

gettime(&t1); // фиксируем начальное время

for (c = 0; c < SortCount; c++) {

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

arRes[i] = arA[i];

for (i = 0; i < arSizes[CurSize]; i++) { //цикл перебора всех элементов

k = i;

x= arRes[i];

for ( j = i + 1; j < arSizes[CurSize]; j++) { // цикл выбора наименьшего элемента

if (arRes[j] < x ) {

k = j;

x = arRes[j]; // k - индекс наименьшего элемента

}

}

arRes[k] = arRes[i]; arRes[i] = x; // меняем местами наименьший с a[i]

}

}

gettime(&t2); // фиксируем конечное время

Eff = (Compares + Changes*10); // считаем условную эффективность

// считаем разницу между начальным и конечным временем с переводом в секунды

T_sort = (t2.ti_hour*360000.+t2.ti_min*6000.+ t2.ti_sec*100.+t2.ti_hund-(t1.ti_hour*360000.+ t1.ti_min*6000.+t1.ti_sec*100.+t1.ti_hund))/100.;

// для достоверности результатов, вычтем из результата время, потраченное на копирование из массива в массив при каждой новой сортировке

T_sort = T_sort - t_copy;

}

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

// функция сортировки методом Вставки с кол-вом повторений сортировок SortCount раз

// параметры: arA[] - исх.массив, arRes[] - массив с результатом

// arSize - кол-во эл. массива,

// Compares - возвращает кол-во операций сравнения

// Changes - возвращает кол-во операций присваивания

// Eff - эффективность алгоритма = (Compares + Changes*10)

// T_sort - время в секундах, затраченное на сортировку

void MInsert(short arA[], short arRes[], int arSize, unsigned int& Compares, unsigned int& Changes, int& Eff, double& T_sort)

{

struct time t1,t2; // структура для замера времени выполнения сортировки

int i,j,k,x,backup;

unsigned int c;

Compares = 0;

Changes = 0;

if (t_copy == -1.00)

GetTcopy(); // замеряем время копирования из одного массива в другой, если оно не было замерено ранее

// производим сортировку один раз для подсчета кол-ва Сравнений и Присваиваний

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

arRes[i] = arA[i]; // скопируем содержимое исх.массива в массив с результатом

backup = arRes[0]; // сохраним старый первый элемент

arRes[0] = -32768; // заменим значение первого элемента на минимальное

Changes += 2; // увеличим счетчик присваиваний на 2, после 2 присваиваний

// начнем сортировку

Compares++; // увеличим счетчик сравнений перед сравнением условия выхода из цикла в след.строке

Changes++; //увеличим счетчик присваиваний перед предстоящим присваиванием начального значения для счетчика цикла

for (i = 1; i < arSizes[CurSize]; i++) { // цикл перебора всех элементов массива со второго элемента

x = arRes[i]; // запомним текущий элемент

Changes++; //увеличим счетчик присваиваний, после присваивания в пред.строке

Compares++; // увеличим счетчик сравнений перед сравнением условия выхода из цикла в след.строке

Changes++; //увеличим счетчик присваиваний перед предстоящим присваиванием начального значения для счетчика цикла

for (j = i-1; arRes[j] > x; j--) {

arRes[j+1] = arRes[j];

Changes++; // увеличиваем счетчик присваиваний после присваивания в пред.строке

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций j

}

arRes[j+1] = x;

Changes++; //увеличим счетчик присваиваний после присваивания в пред.строке

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций i

}

// вставить backup на правильное место

Compares += 2; // увеличим счетчик сравнений на 2 перед сравнением 2-х условий выхода из цикла в след.строке

for (j = 1; j < arSizes[CurSize] && arRes[j] < backup; j++) {

arRes[j-1] = arRes[j];

Changes++; //увеличим счетчик присваиваний после присваивания в пред.строке

Compares += 2; // увеличиваем счетчик сравнений на 2, т.к. для следующей итерации необходимо сравнить 2 условия выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций j

}

// вставка элемента

arRes[j-1] = backup;

Changes++; //увеличим счетчик присваиваний после присваивания в пред.строке

// сортировка закончена

// сортировка SortCount раз с фиксированием времени выполнения

gettime(&t1); // фиксируем начальное время сортировки

for (c=0; c < SortCount; c++) { // цикл прохождения сортировок SortCount раз

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

arRes[i] = arA[i]; // скопируем содержимое исх.массива в массив с результатом

backup = arRes[0]; // сохранить старый первый элемент

arRes[0] = -32768; // заменить на минимальный

// отсортировать массив

for (i = 1; i < arSizes[CurSize]; i++) {

x = arRes[i];

for (j = i-1; arRes[j] > x; j--) {

arRes[j+1] = arRes[j];

}

arRes[j+1] = x;

}

// вставить backup на правильное место

for (j = 1; j < arSizes[CurSize] && arRes[j] < backup; j++)

arRes[j-1] = arRes[j];

// вставка элемента

arRes[j-1] = backup;

}

gettime(&t2); // фиксируем конечное время сортировки

Eff = (Compares + Changes*10); // считаем условную эффективность

// считаем разницу между начальным и конечным временем с переводом в секунды

T_sort = (t2.ti_hour*360000.+t2.ti_min*6000.+ t2.ti_sec*100.+t2.ti_hund-(t1.ti_hour*360000.+ t1.ti_min*6000.+t1.ti_sec*100.+t1.ti_hund))/100.;

// для достоверности результатов, вычтем из результата время, потраченное на копирование из массива в массив при каждой новой сортировке

T_sort = T_sort - t_copy;

}

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

// функция сортировки методом Пузырька с кол-вом повторений сортировок SortCount раз

// параметры: arA[] - исх.массив, arRes[] - массив с результатом

// arSize - кол-во эл. массива,

// Compares - возвращает кол-во операций сравнения

// Changes - возвращает кол-во операций присваивания

// Eff - эффективность алгоритма = (Compares + Changes*10)

// T_sort - время в секундах, затраченное на сортировку

void Puzir(short arA[], short arRes[], int arSize, unsigned int& Compares, unsigned int& Changes, int& Eff, double& T_sort)

{

struct time t1,t2; // структура для замера времени выполнения сортировки

int i,j;

short x;

unsigned int c;

Compares = 0;

Changes = 0;

if (t_copy == -1.00)

GetTcopy(); // замеряем время копирования из одного массива в другой, если оно не было замерено ранее

// производим сортировку один раз для подсчета кол-ва Сравнений и Присваиваний

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

arRes[i] = arA[i]; // скопируем содержимое исх.массива в массив с результатом

// начнем сортировку

Compares++; // увеличим счетчик сравнений перед сравнением условия выхода из цикла в след.цикле

Changes++; //увеличим счетчик присваиваний перед предстоящим присваиванием начального значения для счетчика цикла

for (i = 0; i < arSize; i++){ // цикл перебора по всем элементам

Compares++; // увеличим счетчик сравнений перед сравнением условия выхода из цикла в след.цикле

Changes++; //увеличим счетчик присваиваний перед предстоящим присваиванием начального значения для счетчика цикла

for (j = arSize-1; j > i; j--) { // в цикле перебираем в обратном направлении для каждой родительской итерации

Compares++; //увеличиваем счетчик сравнений перед предстоящим сравнением

if (arRes[j] < arRes[j-1]) { // если последний элемент меньше предпоследнего

// .. то меняем их местами

x = arRes[j-1];

arRes[j-1] = arRes[j];

arRes[j] = x;

Changes+=3; // увеличиваем счетчик присваиваний на 3 после предыдущих 3-х присваиваний

}

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций j

}

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

Changes++; // увеличиваем счетчик присваиваний, т.к. при след.итерации мы увеличим счетчик итераций i

}

//сортировка закончена

// сортировка SortCount раз с фиксированием времени выполнения

gettime(&t1); // фиксируем начальное время сортировки

for (c = 0; c < SortCount; c++) {

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

arRes[i] = arA[i];

for (i = 0; i < arSize; i++){

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

if (arRes[j] < arRes[j-1]) {

x = arRes[j-1];

arRes[j-1] = arRes[j];

arRes[j] = x;

}

}

}

}

gettime(&t2); // фиксируем конечное время сортировки

Eff = (Compares + Changes*10); // считаем условную эффективность

// считаем разницу между начальным и конечным временем с переводом в секунды

T_sort = (t2.ti_hour*360000.+t2.ti_min*6000.+ t2.ti_sec*100.+t2.ti_hund-(t1.ti_hour*360000.+ t1.ti_min*6000.+t1.ti_sec*100.+t1.ti_hund))/100.;

// для достоверности результатов, вычтем из результата время, потраченное на копирование из массива в массив перед каждой новой сортировкой

T_sort = T_sort - t_copy;

}

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

// функция сортировки Быстрым методом с подсчетом кол-ва сравнений и присваиваний

// last - последний элемент массива

// Compares - возвращает кол-во операций сравнения

// Changes - возвращает кол-во операций присваивания

void QuickSortWithCalc(short array[], int last, unsigned int& Compares, unsigned int& Changes)

{

long i = 0, j = last; // поставить указатели на исходные места

Changes++; // увеличиваем счетчик присваиваний после пред.присваивания

short temp, p;

p = array[ last>>1 ]; // центральный элемент

Changes++; // увеличиваем счетчик присваиваний после пред.присваивания

// процедура разделения

do {

Compares++; // увеличиваем счетчик сравнений перед сравнением условия выхода из цикла далее

while ( array[i] < p ) {

i++;

Changes++; // увеличиваем счетчик присваиваний после пред.присваивания i

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

}

Compares++; // увеличиваем счетчик сравнений перед сравнением условия выхода из цикла далее

while ( array[j] > p ) {

j--;

Changes++; // увеличиваем счетчик присваиваний после пред.присваивания j

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла

}

Compares++; // увеличиваем счетчик сравнений перед предстоящим сравнением условия

if (i <= j) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

i++;

j--;

Changes+= 5; // увеличиваем на 5 счетчик присваиваний после пред. пяти присваиваний

}

Compares++; // увеличиваем счетчик сравнений, т.к. для следующей итерации необходимо сравнить условие выхода из цикла далее

} while ( i<=j );

// рекурсивные вызовы, если есть, что сортировать

Compares++; // увеличиваем счетчик сравнений перед предстоящим сравнением условия

if ( j > 0 ) QuickSortWithCalc(array, j, Compares, Changes);

Compares++; // увеличиваем счетчик сравнений перед предстоящим сравнением условия

if ( last > i ) QuickSortWithCalc(array+i, last-i, Compares, Changes);

}

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

// функция сортировки Быстрым методом без подсчетов эффективности

// last - последний элемент массива

void QuickSort(short array[], int last)

{

long i = 0, j = last; // поставить указатели на исходные места

short temp, p;

p = array[ last>>1 ]; // центральный элемент

// процедура разделения

do {

while ( array[i] < p ) i++;

while ( array[j] > p ) j--;

if (i <= j) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

i++;

j--;

}

} while ( i<=j );

// рекурсивные вызовы, если есть, что сортировать

if ( j > 0 ) QuickSort(array, j);

if ( last > i ) QuickSort(array+i, last-i);

}

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

// функция сортировки Быстрым методом с кол-вом повторений сортировок SortCount раз

// параметры: arA[] - исх.массив, arRes[] - массив с результатом

// arSize - кол-во эл. массива,

// Compares - возвращает кол-во операций сравнения

// Changes - возвращает кол-во операций присваивания

// Eff - эффективность алгоритма = (Compares + Changes*10)

// T_sort - время в секундах, затраченное на сортировку

void MQuickSort(short arA[], short arRes[], int arSize, unsigned int& Compares, unsigned int& Changes, int& Eff, double& T_sort)

{

struct time t1,t2; // структура для замера времени выполнения сортировки

int i,j;

short x;

unsigned int c;

Compares = 0;

Changes = 0;

if (t_copy == -1.00)

GetTcopy(); // замеряем время копирования из одного массива в другой, если оно не было замерено ранее

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

arRes[i] = arA[i]; // скопируем содержимое исх.массива в массив с результатом

// производим сортировку один раз для подсчета кол-ва Сравнений и Присваиваний

QuickSortWithCalc(arRes, arSize-1, Compares, Changes);

// сортировка SortCount раз с фиксированием времени выполнения

gettime(&t1); // фиксируем начальное время сортировки

for (c = 0; c < SortCount; c++) { // цикл прохождения сортировок SortCount раз

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

arRes[i] = arA[i]; // скопируем содержимое исх.массива в массив с результатом

QuickSort(arRes, arSize - 1); // отсортируем массив с результатом

}

gettime(&t2); // фиксируем конечное время сортировки

Eff = (Compares + Changes*10); // считаем условную эффективность

// считаем разницу между начальным и конечным временем с переводом в секунды

T_sort = (t2.ti_hour*360000.+t2.ti_min*6000.+ t2.ti_sec*100.+t2.ti_hund-(t1.ti_hour*360000.+ t1.ti_min*6000.+t1.ti_sec*100.+t1.ti_hund))/100.;

// для достоверности результатов, вычтем из результата время, потраченное на копирование из массива в массив перед каждой новой сортировкой

T_sort = T_sort - t_copy;

}

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

// вывод инфо о текущей операции

// параметры: Met - метод сортировки, о котором будет выводиться инфо

// CurFill - порядок заполнения (случ. или убывающ.)

void PutTextCurOperation(short Met, short CurFill)

{

Form1->lbText->Visible = false; // скрываем текстовую инфу рядом с кнопкой "Все сразу"

Form1->lbWait->Visible = true; // вместо нее, показываем надпись "Ждите"

Form1->lbCurMethod->Caption = Form1->Methods[Met].Name; // Выводим на экран название текущего метода

Form1->lbCurSize->Caption = arSizes[CurSize]; // выводим на экран текущую размерность

// выводим на экран текущий порядок заполнения (случ. или убывающ.)

if (CurFill == 0)

Form1->lbCurFill->Caption = "Уб.";

else

Form1->lbCurFill->Caption = "Сл.";

Form1->Refresh(); // перересовываем форму

}

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

// удаление инфо о текущей операции

void ClearTextCurOperation()

{

Form1->lbWait->Visible = false; // скрываем надпись "Ждите" рядом с кнопкой "Все сразу"

Form1->lbText->Visible = true; // вместо нее показываем текстовую инфу, которая была здесь ранее

// очищаем инфо о текущей операции

Form1->lbCurMethod->Caption = "";

Form1->lbCurSize->Caption = "";

Form1->lbCurFill->Caption = "";

Form1->Refresh(); // перересовываем форму

}

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

// функция проверки на прохождение всех сортировок

// если все сортировки пройдены, будет доступна кнопка вывода графика

void CheckAllPassed()

{

short i,j; // счетчики циклов

bool Pass = true; // устанавливаем флаг прохождения всех сортировок в true

for (i = 2; i < 10; i++) // цикл столбцов

for (j = 1; j < 17; j++) // цикл строк

if (Form1->StringGrid1->Cells[i][j] == "") // если какая-нибудь ячейка пуста ..

Pass = false; // то устанавливаем флаг прохождения сортировок в false

if (Pass == true) // если таблица полностью заполнена ..

Form1->btGraf->Enabled = true; // то делаем доступной кнопку вывода графика

}

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

// обнуляем Прогресс-бар и показываем его

void ProgressBarInit()

{

Form1->ProgressBar1->Position = 0; // сбрасываем текущую позицию прогресс-бара

Form1->ProgressBar1->Max = arSizes[CurSize] * 2; // устанавливаем максимальное значение прогресс-бара

Form1->ProgressBar1->Visible = true; // показываем прогресс-бар

}

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

//сортировка массива текущей размерности для убывающей и случайного порядков

//Параметры: SortMethod - метод сортировки: 0 - Отбор, 1 - Вставки, 2 - Пузырек, 3 - Быстрый

void DoSort(short SortMethod)

{

unsigned int Comp[2],Chang[2]; // массивы с двумя элементами для фиксации кол-ва сравнений и присваиваний для убыв. и случ. порядков

int ef[2]; // массив с двумя элементами для фиксации эффективности для убыв. и случ. порядков

double Tsort[2]; // массив с двумя элементами для фиксации времени выполнения для убыв. и случ. порядков

PutTextCurOperation(SortMethod,0); // выводим на экран инфо о текущей операции (убыв.порядок)

// сортировка массива в случ.порядке методом отбора

if (SortMethod == 0)

MSelect(&arSource[0][CurSize][0],&arRes[0][0],arSizes[CurSize],Comp[0],Chang[0],ef[0],Tsort[0]);

// сортировка массива в случ.порядке методом вставки

if (SortMethod == 1)

MInsert(&arSource[0][CurSize][0],&arRes[0][0],arSizes[CurSize],Comp[0],Chang[0],ef[0],Tsort[0]);

// сортировка массива в случ.порядке методом пузырька

if (SortMethod == 2)

Puzir(&arSource[0][CurSize][0],&arRes[0][0],arSizes[CurSize],Comp[0],Chang[0],ef[0],Tsort[0]);

// сортировка массива в случ.порядке быстрым методом

if (SortMethod == 3)

MQuickSort(&arSource[0][CurSize][0],&arRes[0][0],arSizes[CurSize],Comp[0],Chang[0],ef[0],Tsort[0]);

Form1->ProgressBar1->StepBy(arSizes[CurSize]); // продвигаем прогресс-бар на текущую размерность

PutTextCurOperation(SortMethod,1); // выводим на экран инфо о текущей операции (случ.порядок)

// сортировка массива в убыв.порядке методом отбора

if (SortMethod == 0)

MSelect(&arSource[1][CurSize][0],&arRes[1][0],arSizes[CurSize],Comp[1],Chang[1],ef[1],Tsort[1]);

// сортировка массива в убыв.порядке методом вставки

if (SortMethod == 1)

MInsert(&arSource[1][CurSize][0],&arRes[1][0],arSizes[CurSize],Comp[1],Chang[1],ef[1],Tsort[1]);

// сортировка массива в убыв.порядке методом пузырька

if (SortMethod == 2)

Puzir(&arSource[1][CurSize][0],&arRes[1][0],arSizes[CurSize],Comp[1],Chang[1],ef[1],Tsort[1]);

// сортировка массива в убыв.порядке быстрым методом

if (SortMethod == 3)

MQuickSort(&arSource[1][CurSize][0],&arRes[1][0],arSizes[CurSize],Comp[1],Chang[1],ef[1],Tsort[1]);

Form1->ProgressBar1->StepBy(arSizes[CurSize]); // продвигаем прогресс-бар на текущую размерность

PutResAr(SortMethod,Comp,Chang,ef,Tsort); // выводим на экран результат сортировки

}

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

//функция для обработки событий от кнопок (Пузырек, Вставки, Отбор, Быстрая)

//сортировка массива текущей размерности для убывающей и случайного порядков

//эта функция вызывает DoSort, а также очищает Прогресс-бар, удаляет ранее отсортированный массив и пр.

//Параметры: SortMethod - метод сортировки: 0 - Отбор, 1 - Вставки, 2 - Пузырек, 3 - Быстрый

void DoSortForCommandButtons(short SortMethod)

{

ClearSorted(); // очищаем ранее выведенную статистику для отсортированных массивов

ProgressBarInit(); // обнуляем Прогресс-бар и показываем его

DoSort(SortMethod); // сортируем исх.массив для убывающего и случайного порядков

ClearTextCurOperation(); // очищаем инфо о текущей операции

CheckAllPassed(); // проверяем, пройдены ли все сортировки. Если пройдены, делаем доступной кнопку вывода графика

Form1->ProgressBar1->Visible = false; // скрываем прогресс-бар

}

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

// обработка кнопки "Отбор"

void __fastcall TForm1::btSelectClick(TObject *Sender)

{

// сортируем исх.массив методом Отбора для убывающего и случайного порядков

DoSortForCommandButtons(0);

}

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

// обработка кнопки "Вставки"

void __fastcall TForm1::btInsertClick(TObject *Sender)

{

// сортируем исх.массив методом Вставки для убывающего и случайного порядков

DoSortForCommandButtons(1);

}

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

// обработка кнопки "Пузырек"

void __fastcall TForm1::btPuzirClick(TObject *Sender)

{

// сортируем исх.массив методом Пузырька для убывающего и случайного порядков

DoSortForCommandButtons(2);

}

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

// обработка кнопки "Быстрая"

void __fastcall TForm1::btQuickClick(TObject *Sender)

{

// сортируем исх.массив Быстрым методом для убывающего и случайного порядков

DoSortForCommandButtons(3);

}

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

// обработка кнопки "Все сразу"

// прохождение всех сортировок в авто-режиме

void __fastcall TForm1::btAllSortClick(TObject *Sender)

{

short i; // счетчик циклов

// устанавливаем максимальное значение прогресс-бара (сумма всех размерностей)

Form1->ProgressBar1->Max = 0;

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

Form1->ProgressBar1->Max += arSizes[i]*8;

ClearStat(); // удаляем всю раннее выведенную статистику

Form1->ProgressBar1->Visible = true; // показываем прогресс-бар

// цикл прохождения по всем размерностям

for (CurSize = 0; CurSize <= 3; CurSize++) {

// переключаем радио-кнопки выбора размерности, в зависимости от текущей размерности

switch (CurSize) {

case 0:

Form1->RadioButton1->Checked = true;

break;

case 1:

Form1->RadioButton2->Checked = true;

break;

case 2:

Form1->RadioButton3->Checked = true;

break;

case 3:

Form1->RadioButton4->Checked = true;

break;

}

ClearSorted(); // удаляем с экрана отсортированные массивы

// выполняем сортировки по всем методам

for (i = 0; i <= 3; i++) {

DoSort(i);

}

Form1->Refresh(); // перересовываем форму

}

// после прохождения всех сортировок ..

Form1->ProgressBar1->Visible = false; // скрываем прогресс-бар

ClearTextCurOperation(); // удаляем инфо о текущей операции

btGraf->Enabled = true; // делаем доступной кнопку вывода графика

}

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

// обработка кнопки "График"

// вывод окна с графиком результатов сортировки

void __fastcall TForm1::btGrafClick(TObject *Sender)

{

GrafForm->ShowModal();

}

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

// исли пользователь изменил строку поиска, обнуляем статистику поиска

void __fastcall TForm1::edWhatChange(TObject *Sender)

{

Form1->edDirectCompSource->Text = "";

Form1->edDirectICountSource->Text = "";

Form1->edDirectFoundPosSource->Text = "";

Form1->edDirectComp->Text = "";

Form1->edDirectICount->Text = "";

Form1->edDirectFoundPos->Text = "";

Form1->edBinComp->Text = "";

Form1->edBinICount->Text = "";

Form1->edBinFoundPos->Text = "";

Form1->edIntComp->Text = "";

Form1->edIntICount->Text = "";

Form1->edIntFoundPos->Text = "";

Form1->lbToFind->Caption = Form1->edWhat->Text;

}

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

// фильтр TEdit для ввода только цифр (для ПОИСКА чисел в массиве)

void __fastcall TForm1::edWhatKeyPress(TObject *Sender, char &Key)

{

if (!(((Key >= '0') && (Key <= '9')) || (Key == VK_BACK)))

Key = 0;

}

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

// фильтр TEdit для ввода только цифр (для задания кол-ва повторений сортировок)

void __fastcall TForm1::edCountKeyPress(TObject *Sender, char &Key)

{

if (!(((Key >= '0') && (Key <= '9')) || (Key == VK_BACK)))

Key = 0;

}

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

// Обработка кнопки Прямой (для неотсортированного массива)

// Поиск значения в массиве прямым перебором

void __fastcall TForm1::btDirectSourceClick(TObject *Sender)

{

// проверяем, введено ли число для его поиска

if (Form1->edWhat->Text == ""){

ShowMessage("Введите число для его поиска в массиве");

return; // выходим из поиска, если число не введено

}

short i; // счетчик цикла

short iCount = 0; // счетчик кол-ва итераций (сравнений)

bool isFound = false; // флаг - найдено или нет

// цикл прямого перебора массива для сравнения с искомым числом

for (i = 0; i < 20; i++) {

iCount++;

// если искомое число совпало с текущим числом в массиве, то ..

if (StrToInt(Form1->edWhat->Text) == StrToInt(Form1->lboxFindSource->Items->Strings[i])) {

Form1->edDirectFoundPosSource->Text = i+1; // выводим найденую позицию

isFound = true; // запоминаем, что число найдено

break; // выходим из цикла прямого перебора

}

}

Form1->edDirectCompSource->Text = iCount; // выводим на экран кол-во сравнений

Form1->edDirectICountSource->Text = iCount; // выводим на экран кол-во итераций

if (isFound == false) //если ничего не было найдено, то

Form1->edDirectFoundPosSource->Text = "Не найдено"; //пишем, "Не найдено"

}

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

// Обработка кнопки Прямой (для отсортированного массива)

// Поиск значения в массиве прямым перебором

void __fastcall TForm1::btDirectClick(TObject *Sender)

{

// проверяем, введено ли число для его поиска

if (Form1->edWhat->Text == ""){

ShowMessage("Введите число для его поиска в массиве");

return; // выходим из поиска, если число не введено

}

short arFindSorted[20]; //объявляем массив в котором будем искать

short i;

// заполняем массив исходными значениями

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

arFindSorted[i] = StrToInt(Form1->lboxFindSource->Items->Strings[i]);

// сортируем массив быстрой сортировкой

QuickSort(&arFindSorted[0],19);

// выводим на экран отсортированный массив

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

Form1->lboxFindSorted->Items->Strings[i] = arFindSorted[i];

short iCount = 0; // счетчик кол-ва итераций (сравнений)

bool isFound = false; // флаг - найдено или нет

// цикл прямого перебора массива для сравнения с искомым числом

for (i = 0; i < 20; i++) {

iCount++;

// если искомое число совпало с текущим числом в массиве, то ..

if (StrToInt(Form1->edWhat->Text) == StrToInt(Form1->lboxFindSorted->Items->Strings[i])) {

Form1->edDirectFoundPos->Text = i+1; // выводим найденую позицию

isFound = true; // запоминаем, что число найдено

break; // выходим из цикла прямого перебора

}

}

Form1->edDirectComp->Text = iCount; // выводим на экран кол-во сравнений

Form1->edDirectICount->Text = iCount; // выводим на экран кол-во итераций

if (isFound == false) //если ничего не было найдено, то

Form1->edDirectFoundPos->Text = "Не найдено"; //пишем, "Не найдено"

}

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

// Обработка кнопки Бинарный

// Поиск значения в массиве Бинарным способом

void __fastcall TForm1::btBinClick(TObject *Sender)

{

// проверяем, введено ли число для его поиска

if (Form1->edWhat->Text == ""){

ShowMessage("Введите число для его поиска в массиве");

return; // выходим из поиска, если число не введено

}

short arFindSorted[20]; //объявляем массив в котором будем искать

short i; // счетчик циклов

short M; // вспомогательная переменная для определения принадлежности к тому или иному диапазону поиска

short Key; // переменная для хранения - что будем искать

short Compares = 0; // счетчик кол-ва сравнений

short iCount = 0; // счетчик кол-ва итераций

bool isFound = false; // флаг - найдено или нет

short Lb = 0; // нижняя граница диапазона поиска

short Ub = 19; // верхняя граница диапахона поиска

// заполняем массив исходными значениями

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

arFindSorted[i] = StrToInt(Form1->lboxFindSource->Items->Strings[i]);

// сортируем массив быстрой сортировкой

QuickSort(&arFindSorted[0],19);

// выводим на экран отсортированный массив

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

Form1->lboxFindSorted->Items->Strings[i] = arFindSorted[i];

// присваиваем переменной Key - что будем искать

Key = StrToInt(Form1->edWhat->Text);

// цикл поиска бинарным методом

do {

iCount++; // увеличиваем счетчик кол-ва итераций

M = (Lb + Ub)/2; //находим середину диапазона поиска

Compares++; //увеличиваем счетчик сравнений перед предстоящим сравнением

// искомое число находится в первой половине диапазона поиска ?

if (Key < arFindSorted[M])

Ub = M - 1; //если да, то присваиваем новую верхнюю границу нового диапазона поиска

else { //если нет, то

Compares++; //увеличиваем счетчик сравнений перед предстоящим сравнением

//искомое число находится во второй половине диапозона поиска ?

if (Key > arFindSorted[M])

Lb = M + 1; //если да, то присваиваем новую нижнюю границу нового диапазона поиска

else { //если нет, т.е. если число совпало с искомым, то ..

Form1->edBinFoundPos->Text = M+1; //выводим на экран найденную позицию

isFound = true; //запоминаем, что число найдено

break; //выходим из цикла поиска

}

}

Compares++; //увеличиваем счетчик сравнений перед предстоящей проверки условия выхода из цикла

}

while (Lb <= Ub);

Form1->edBinComp->Text = Compares; //выводим на экран кол-во сравнений

Form1->edBinICount->Text = iCount; // выводим на экран кол-во итераций

if (isFound == false) //если ничего не было найдено, то

Form1->edBinFoundPos->Text = "Не найдено"; //пишем, "Не найдено"

}

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

// Обработка кнопки "Интерполяция"

// Поиск значения в массиве интерполяционным методом

void __fastcall TForm1::btIntClick(TObject *Sender)

{

// проверяем, введено ли число для его поиска

if (Form1->edWhat->Text == ""){

ShowMessage("Введите число для его поиска в массиве");

return; // выходим из поиска, если число не введено

}

short arFindSorted[20]; //объявляем массив в котором будем искать

short i; // счетчик циклов

short M; // вспомогательная переменная для определения принадлежности к тому или иному диапазону поиска

short Key; // переменная для хранения - что будем искать

short Compares = 0; // счетчик кол-ва сравнений

short iCount = 0; // счетчик кол-ва итераций

bool isFound = false; // флаг - найдено или нет

short Lb = 0; // нижняя граница диапазона поиска

short Ub = 19; // верхняя граница диапахона поиска

// заполняем массив исходными значениями

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

arFindSorted[i] = StrToInt(Form1->lboxFindSource->Items->Strings[i]);

// сортируем массив быстрой сортировкой

QuickSort(&arFindSorted[0],19);

// выводим на экран отсортированный массив

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

Form1->lboxFindSorted->Items->Strings[i] = arFindSorted[i];

// присваиваем переменной Key - что будем искать

Key = StrToInt(Form1->edWhat->Text);

// цикл поиска интерполяционным методом

Compares ++; // увеличиваем счетчик сравнений перед предстоящей проверкой условия выхода из цикла

while(Lb<Ub) // если верхняя граница станет меньше нижней, то выйдем из цикла

{

iCount++; // счетчик итераций цикла

// расстояние следующей пробы от Lb

i = Lb + ((Ub - Lb)*(Key - arFindSorted[Lb])) /(arFindSorted[Ub] - arFindSorted[Lb]);

Compares +=2; // увеличим счетчик перед проверкой след.2 условий

if (i<Lb || i>Ub)

break; // выйдем из цикла, если расчитанное расстояние вышло за рамки искомого диапазона

Compares++; // увеличим счетчик сравнений перед проверкой условия

if(Key<arFindSorted[i]) //если ключ меньше текущей позиции

Ub = i-1; //то изменим верхнюю границу

else {

Compares++; // увеличим счетчик сравнений перед проверкой условия

if(Key>arFindSorted[i]) //если ключ больше текущей позиции

Lb=i+1; // то изменим нижнюю границу

else { // если не больше и не меньше, т.е. равно

isFound = true; // запоминаем, что нашли

break; // и выходм из цикла

}

}

Compares ++; // счетчик проверки выхода из цикла

}

Form1->edIntComp->Text = Compares; //выводим на экран кол-во сравнений

Form1->edIntICount->Text = iCount; // выводим на экран кол-во итераций

if (!isFound) //если ничего не было найдено, то

Form1->edIntFoundPos->Text = "Не найдено"; //пишем, "Не найдено"

else

Form1->edIntFoundPos->Text = i+1;

}

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