ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННИЙ ИНСТИТУТ РАДИОТЕХНИКИ
ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)»
Лабораторная работа №3
По дисциплине
«Технология Программирования»
Студент: Ли С.И.
Группа №: ИТА-1-09
Преподаватель: Торхова Наталья Анатольевна
Москва, 2011
Задание
1) Разработать 3 (4) функции сортировки
2) Просчитать количество операций
3) Рассмотреть критические ситуации на входе
(масcив от сортировался в обратном порядке, когда он отсортирован в нужном порядке, массив пустой, когда в массиве много значений 1000~5000)
4) Сравнить скорость на разных количествах элементов
Алгоритмы: слияние, метод хоара, шелла и метод вставки
Код программы:
Глобальные переменные файла Unit1.h
int * array; // Указатель для динамического массива
/*- Функции сортировки -*/
voidTForm1::SortPusyr();
void TForm1::SortXoar();
void TForm1::SortMarge();
void TForm1::mergeSort(int *a, intlen, TTime time);
int* TForm1::merge(int *m1, int* m2, int l1, int l2);
void TForm1::SortQuick1(int *, int, int);
void TForm1::SortQuick2(int *, int, int, TTime);
void TForm1::SortInsert();
void TForm1::SortShell();void TForm1::SortInsert();
voidTForm1::SortShell();
/*- .Функции сортировки -*/
// Функция возвращает массив в виде текста
String TForm1::Print(int *);
/*- Дляпотоков -*/
static DWORD __stdcall TForm1::SortP(LPVOID);
static DWORD __stdcall TForm1::SortX(LPVOID);
static DWORD __stdcall TForm1::SortI(LPVOID);
static DWORD __stdcall TForm1::SortS(LPVOID);
static DWORD __stdcall TForm1::StartChek(LPVOID);
HANDLE hthread1,hthread2,hthread3,hthread4,hthread5;
boolok[4];
/*- .Для потоков -*/
/*- Счетчики -*/
intCountOpX;
intCountOpP;
intCountOpI;
intCountOpS;
String TForm1::FormatInt(double);
/*- .Счетчики -*/
Код программы Unit1.cpp
// ---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include <math.h>
#include "Unit1.h"
// ---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include <math.h>
#include "Unit1.h"
// ---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
// ---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) {
}
// ---------------------------------------------------------------------------
// Функциясозданиямассива
void __fastcall TForm1::CreateMasClick(TObject *Sender) {
delete[]array;
array = new int[EMn->Text.ToInt()];
srand(time(NULL));
for (inti = 0; i<EMn->Text.ToInt(); i++) {
array[i] = rand() % EMaxNumber->Text.ToInt()+1;
if (CNegative->Checked) {
if (rand() % 4 == 1)
array[i] = -array[i];
}
}
Memo1->Lines->Text = Print(array);
Start->Enabled = true;
}
// ---------------------------------------------------------------------------
// Функция возвращает массив в виде текста
String TForm1::Print(int *mas) {
String result;
for (inti = 0; i<EMn->Text.ToInt(); i++) {
result = result + (String)mas[i] + " ";
}
returnresult;
}
// ---------------------------------------------------------------------------
// Функция для вызова сортировки по методу хоара
Void tForm1::SortXoar() {
TTime time;
time = Time();
int *mas = new int[EMn->Text.ToInt()];
for (inti = 0; i<EMn->Text.ToInt(); i++)
mas[i] = array[i];
if (CRealTime->Checked)
SortQuick2(mas, 0, EMn->Text.ToInt() - 1, time);
else
SortQuick1(mas, 0, EMn->Text.ToInt() - 1);
time = Time() - time;
LTimeX->Caption = time.FormatString("nn:ss:zz");
Memo3->Lines->Text = Print(mas);
LOpX->Caption = FormatInt(CountOpX);
delete[]mas;
}
// ---------------------------------------------------------------------------
// Функция сортировки хоара без мониторинга процесса сортировки
void TForm1::SortQuick1(int *mas, int left, int right) {
inti = left;
int j = right;
int x = mas[(left + right)/2];
CountOpX += 3;
do {
CountOpX += 1;
while (mas[i] < x) {
++i; CountOpX += 2; }
while (x < mas[j]){
--j; CountOpX += 2; }
if ( i <= j ) { CountOpX += 1;
if( i < j ) { CountOpX += 4;
int t = mas[i];
mas[i] = mas[j];
mas[j] = t;
}
++i;
--j;
CountOpX += 2;
}
} while (i <= j);
CountOpX += 2;
if (left < j)
SortQuick1(mas, left, j);
if (i < right)
SortQuick1(mas, i, right);
}
// ---------------------------------------------------------------------------
// Функция сортировки хоара с выводом информации о процессе сортировки
void TForm1::SortQuick2(int *mas, int left, int right, TTime time) {
inti = left;
int j = right;
int x = mas[(left + right)/2];
CountOpX += 3;
TTime temp;
do {
CountOpX += 1;
while (mas[i] < x) {
++i; CountOpX += 2; }
while (x < mas[j]){
--j; CountOpX += 2; }
if ( i <= j ) { CountOpX += 1;
if( i < j ) { CountOpX += 4;
int t = mas[i];
mas[i] = mas[j];
mas[j] = t;
temp = Time() - time;
LTimeX->Caption = temp.FormatString("nn:ss:zz");
Memo3->Lines->Text = Print(mas);
LOpX->Caption = FormatInt(CountOpX);
LOpX->Refresh();
LTimeX->Refresh();
Memo3->Refresh();
}
++i;
--j;
CountOpX += 2;
}
} while (i <= j);
CountOpX += 2;
if (left < j)
SortQuick2(mas, left, j,time);
if (i < right)
SortQuick2(mas, i, right,time);
}
// ---------------------------------------------------------------------------
// Сортировкаметодомслияния
Void tForm1::SortMarge() {
TTime time= Time();
int * a = new int[EMn->Text.ToInt()];
for (inti = 0; i<EMn->Text.ToInt(); i++)
a[i] = array[i];
mergeSort(a, EMn->Text.ToInt(), time);
time = Time() - time;
LTimeP->Caption = time.FormatString("nn:ss:zz");
Memo2->Lines->Text = Print(a);
LOpP->Caption = FormatInt(CountOpP);
delete[]a;
}
// ---------------------------------------------------------------------------
void TForm1::mergeSort(int *mas, intlen,TTime time) {
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
TTime temp;
int n=1, l, ost;
int * mas1;
while (n<len){
l=0; CountOpP+=2;
while (l<len)
{
if (l+n>= len) break; CountOpP+=2;
// ost = (l+n*2>len) ? (len-(l+n)) : n; CountOpP+=2;
if(l+n*2>len)
ost=len-(l+n);
else
ost=n;
CountOpP+=2;
mas1 = merge(mas+l, mas+l+n, n, ost);
for (inti=0; i<n+ost; i++){ mas[l+i] = mas1[i]; CountOpP+=3;
if (CRealTime->Checked) {
temp = Time() - time;
LTimeP->Caption = temp.FormatString("nn:ss:zz");
Memo2->Lines->Text = Print(mas);
LOpP->Caption = FormatInt(CountOpP);
Memo2->Refresh();
LOpP->Refresh();
LTimeP->Refresh();
}
}
delete [] mas1;
l+=n*2; CountOpP+=2;
}
n*=2;
}
}
// ---------------------------------------------------------------------------