Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Файл 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;
}
//---------------------------------------------------------------------------
|
|