Сортировки Числовых Массивов.

  • Автор темы Miller85
  • Дата начала
M

Miller85

#1
Всем привет! Нужна помощь!
Задание:

1) Отсортировать по возрастанию числовой массив обменами, выбором, вставками, пузырьком и быстрой сортировкой. Получить зависимости временных затрат от размера массива. Временные затраты оценивать количеством сравнений и количеством обменов элементов массива. Сортировку выполнять на месте исходного массива.

вот мой код:
загаловочный (.h):
C++:
#ifndef LR_3H
#define LR_3H
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include "CSPIN.h"
#include <ComCtrls.hpp>
#include <Menus.hpp>
#include <Buttons.hpp>
#include <ExtCtrls.hpp>
#include <Grids.hpp>
#include <Chart.hpp>
#include <TeEngine.hpp>
#include <TeeProcs.hpp>
#include <Series.hpp>
#include <Dialogs.hpp>
#include <ExtDlgs.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:	// IDE-managed Components
TMainMenu *MainMenu1;
TMenuItem *file;
TMenuItem *N2;
TMenuItem *N3;
TMenuItem *sort;
TMenuItem *rec;
TMenuItem *rep;
TMenuItem *help;
TMenuItem *exit;
TGroupBox *GroupBox1;
TGroupBox *GroupBox2;
TLabel *Label1;
TLabel *Label2;
TLabel *Label3;
TPageControl *PageControl1;
TTabSheet *TabSheet1;
TTabSheet *TabSheet2;
TCSpinEdit *CSpinEdit1;
TCSpinEdit *CSpinEdit2;
TCSpinEdit *CSpinEdit3;
TCSpinEdit *CSpinEdit4;
TCSpinEdit *CSpinEdit5;
TLabel *Label4;
TLabel *Label5;
TLabel *Label6;
TCSpinEdit *CSpinEdit6;
TPanel *Panel1;
TBitBtn *BitBtn1;
TMemo *Memo1;
TStringGrid *StringGrid1;
TStringGrid *StringGrid2;
TProgressBar *ProgressBar1;
TCSpinEdit *CSpinEdit7;
TTabSheet *TabSheet3;
TTabSheet *TabSheet4;
TTabSheet *TabSheet5;
TTabSheet *TabSheet6;
TTabSheet *TabSheet7;
TChart *Chart5;
TLineSeries *Series9;
TLineSeries *Series10;
TChart *Chart4;
TLineSeries *Series7;
TLineSeries *Series8;
TChart *Chart3;
TLineSeries *Series5;
TLineSeries *Series6;
TChart *Chart1;
TLineSeries *Series1;
TLineSeries *Series2;
TChart *Chart2;
TLineSeries *Series3;
TLineSeries *Series4;
TImage *Image1;
TImage *Image2;
TImage *Image3;
TImage *Image4;
TImage *Image5;
TPopupMenu *PopupMenu1;
TPopupMenu *PopupMenu2;
TPopupMenu *PopupMenu3;
TPopupMenu *PopupMenu4;
TPopupMenu *PopupMenu5;
TMenuItem *N1;
TMenuItem *N4;
TMenuItem *N5;
TMenuItem *N6;
TMenuItem *N7;
TMenuItem *N8;
TMenuItem *N9;
TMenuItem *N10;
TMenuItem *N11;
TMenuItem *N12;
TLabel *Label7;
TLabel *Label8;
TLabel *Label9;
TGroupBox *GroupBox3;
void __fastcall exitClick(TObject *Sender);
void __fastcall BitBtn1Click(TObject *Sender);
void __fastcall recClick(TObject *Sender);
void __fastcall N2Click(TObject *Sender);
void __fastcall N3Click(TObject *Sender);
void __fastcall N1Click(TObject *Sender);
void __fastcall N4Click(TObject *Sender);
void __fastcall N5Click(TObject *Sender);
void __fastcall N6Click(TObject *Sender);
void __fastcall N7Click(TObject *Sender);
void __fastcall N8Click(TObject *Sender);
void __fastcall N9Click(TObject *Sender);
void __fastcall N10Click(TObject *Sender);
void __fastcall N11Click(TObject *Sender);
void __fastcall N12Click(TObject *Sender);
void __fastcall helpClick(TObject *Sender);
private:	// User declarations
public:		// User declarations
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
class array{
public:
array(int);				  //конструктор 1 (с параметром)
array(array&);				//конструктор 2 (копии)
void swap(int&,int&);	  //обмен элементов в сортируемом массиве
void SwapSort(int,int,int);		 //сортировка обменами
void SelectSort(int,int,int,int);	 //сортировка выбором
void InsertSort(int,int,int,array&); //сортировка вставками
void BubbleSort(int,int,int,int);	//сортировка пузырьком
void QuickSort(int,int,int);		 //быстрая сортировка
void out_mass_a()const; //вывод исходного и отсортированного массивов
int get_sr()const{return sr;} //получить сравнения
int get_obm()const{return obm;}//получить обмены
~array(){delete[]a;}		 //деструктор
private:
int*a, //указатель для исходного сортируемого массива
sr, //сравнения
obm, //обмены
n;  //размер исходного сортируемого массива
};
#endif
Программа:
C++:
#include <vcl.h>
#pragma hdrstop

#include "LR_3.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma link "CSPIN"
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
int razm_min,razm_max,d,m,max_d,min_d,razm_out,t;
//---------------------------------------------------------------------------
array::array(int p)
{n=p;
a=new int[n];
sr=0;
obm=0;
for(int i=0;i<n;i++) a[i]=random(max_d-min_d+1)+min_d;
}
//---------------------------------------------------------------------------
array::array(array&c)
{n=c.n; sr=c.sr; obm=c.obm;
a=new int[n];
for(int i=0;i<n;i++)a[i]=c.a[i];
}
//---------------------------------------------------------------------------
void array::swap(int&x,int&y)
{int z=x;x=y;y=z;}
//---------------------------------------------------------------------------
void array::SwapSort(int i,int j,int k)
{ if(i==n-1) return;
if(j<n) {
if(a[i]>a[j]) {swap(a[i],a[j]); obm++;}
sr++; SwapSort(i,j+1,k);
}
else SwapSort(i+1,i+2,k);
}
//---------------------------------------------------------------------------
void array::SelectSort(int i,int j,int min,int k)
{ if(i==n-1) return;
if(j<n) {
if(a[min]>a[j]) min=j;
sr++; SelectSort(i,j+1,min,k);
}
else {
swap(a[i],a[min]); obm++;
SelectSort(i+1,i+2,i+1,k);
}
}
//---------------------------------------------------------------------------
void array::InsertSort(int i,int j,int k,array&c)
{ if(i==n) return;
int z=c.a[i];
if(j>0&&z<a[j-1]) {
a[j]=a[j-1]; sr++;
InsertSort(i,j-1,k,c);
}
else {
a[j]=z; sr++;
InsertSort(i+1,i+1,k,c);
}
}
//---------------------------------------------------------------------------
void array::BubbleSort(int i,int j,int last,int k)
{ if(i<=0) return;
if(j<i) {
if(a[j]>a[j+1]) {swap(a[j],a[j+1]); obm++; last=j;}
sr++; BubbleSort(i,j+1,last,k);
}
else BubbleSort(last,0,0,k);
}
//---------------------------------------------------------------------------
void array::QuickSort(int l,int h,int k)
{ int su,sd,m,p;
if(h-l<=0) return;
else if(h-l==1) {
if(a[h]<a[l]) {swap(a[l],a[h]); obm++;}
sr++;
return;
}
m=(l+h)/2; p=a[m]; swap(a[m],a[l]); obm++; su=l+1;sd=h;
do{
while(su<=sd && a[su]<=p) {su++; sr++;}
while(p<a[sd]) {sd--; sr++;}
if(su<sd) {swap(a[su],a[sd]); obm++; }
} while(su<sd);
a[l]=a[sd]; a[sd]=p; obm++;
if(l<sd-1) QuickSort(l,sd-1,k);
if(sd+1<h) QuickSort(sd+1,h,k);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::exitClick(TObject *Sender)
{
Close();
}

//---------------------------------------------------------------------------
void array::out_mass_a()const
{
AnsiString str="";
for(int i=0;i<n;i++)str+="  "+IntToStr(a[i]);
Form1->Memo1->Lines->Add(str);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn1Click(TObject *Sender)
{
Memo1->Clear();
Panel1->Caption="";
for(int i=0;i<StringGrid1->RowCount;i++)
for(int j=0;j<StringGrid1->ColCount;j++)
{StringGrid1->Cells[j][i]="";
StringGrid2->Cells[j][i]="";}
StringGrid1->Cells[0][0]="размер";
StringGrid1->Cells[1][0]="обменами";
StringGrid1->Cells[2][0]="выбором";
StringGrid1->Cells[3][0]="вставками";
StringGrid1->Cells[4][0]="пузырьком";
StringGrid1->Cells[5][0]="быстрая";
StringGrid2->Cells[0][0]="размер";
StringGrid2->Cells[1][0]="обменами";
StringGrid2->Cells[2][0]="выбором";
StringGrid2->Cells[3][0]="вставками";
StringGrid2->Cells[4][0]="пузырьком";
StringGrid2->Cells[5][0]="быстрая";
Series1->Clear();
Series2->Clear();
Series3->Clear();
Series4->Clear();
Series5->Clear();
Series6->Clear();
Series7->Clear();
Series8->Clear();
Series9->Clear();
Series10->Clear();
ProgressBar1->Position=0;
if(CSpinEdit1->Value>CSpinEdit2->Value){Panel1->Caption=
"мин размер не м б больше макс!"; return;}
if(CSpinEdit5->Value>CSpinEdit4->Value){Panel1->Caption=
"мин число не м б больше макс!"; return;}
if(CSpinEdit7->Value%CSpinEdit3->Value){Panel1->Caption=
"t/d должно быть целым!"; return;}
razm_min=CSpinEdit1->Value;
razm_max=CSpinEdit2->Value;
d=CSpinEdit3->Value;
m=(razm_max-razm_min)/d+1;
max_d=CSpinEdit4->Value;
min_d=CSpinEdit5->Value;
razm_out=CSpinEdit6->Value;
t=CSpinEdit7->Value;
sort->Enabled=true;
} 
//---------------------------------------------------------------------------
void __fastcall TForm1::recClick(TObject *Sender)
{
StringGrid1->RowCount=(razm_max-razm_min)/t+2;
StringGrid2->RowCount=(razm_max-razm_min)/t+2;
int count=m,current=0;
for(int k=0;k<m;k++){
array arr(razm_min+k*d);
if(razm_min+k*d==razm_out)
Form1->Memo1->Lines->Add("				Сортировка обменами");
array arr_swap=arr;
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Исходный массив");
arr_swap.out_mass_a();}
arr_swap.SwapSort(0,1,k);
Form1->Series1->AddXY(razm_min+k*d,arr_swap.get_sr(),"",clBlack);
Form1->Series2->AddXY(razm_min+k*d,arr_swap.get_obm(),"",clBlack);
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Отсортированный массив");
arr_swap.out_mass_a();}
if(razm_min+k*d==razm_out)
Form1->Memo1->Lines->Add("				 Сортировка выбором");
array arr_select=arr;
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Исходный массив");
arr_select.out_mass_a();}
arr_select.SelectSort(0,1,0,k);
Form1->Series3->AddXY(razm_min+k*d,arr_select.get_sr(),"",clBlack);
Form1->Series4->AddXY(razm_min+k*d,
arr_select.get_obm()*100,"",clBlack);
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Отсортированный массив");
arr_select.out_mass_a();}
if(razm_min+k*d==razm_out)
Form1->Memo1->Lines->Add("				Сортировка вставками");
array arr_insert=arr;
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Исходный массив");
arr_insert.out_mass_a();}
arr_insert.InsertSort(1,1,k,arr);
Form1->Series5->AddXY(razm_min+k*d,arr_insert.get_sr(),"",clBlack);
Form1->Series6->AddXY(razm_min+k*d,arr_insert.get_obm(),"",clBlack);
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Отсортированный массив");
arr_insert.out_mass_a();}
if(razm_min+k*d==razm_out)
Form1->Memo1->Lines->Add("				Сортировка пузырьком");
array arr_bubble=arr;
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Исходный массив");
arr_bubble.out_mass_a();}
arr_bubble.BubbleSort(razm_min+k*d-1,0,0,k);
Form1->Series7->AddXY(razm_min+k*d,arr_bubble.get_sr(),"",clBlack);
Form1->Series8->AddXY(razm_min+k*d,arr_bubble.get_obm(),"",clBlack);
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Отсортированный массив");
arr_bubble.out_mass_a();}
if(razm_min+k*d==razm_out)
Form1->Memo1->Lines->Add("				Быстрая сортировка");
array arr_quick=arr;
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Исходный массив");
arr_quick.out_mass_a();}
arr_quick.QuickSort(0,razm_min+k*d-1,k);
Form1->Series9->AddXY(razm_min+k*d,arr_quick.get_sr(),"",clBlack);
Form1->Series10->AddXY(razm_min+k*d,arr_quick.get_obm(),"",clBlack);
if(razm_min+k*d==razm_out){
Form1->Memo1->Lines->Add("Отсортированный массив");
arr_quick.out_mass_a();}
if(k*d%t==0){
Form1->StringGrid1->Cells[0][k*d/t+1]=IntToStr(razm_min+k*d);
Form1->StringGrid2->Cells[0][k*d/t+1]=IntToStr(razm_min+k*d);
Form1->StringGrid1->Cells[1][k*d/t+1]=IntToStr(arr_swap.get_sr());
Form1->StringGrid2->Cells[1][k*d/t+1]=IntToStr(arr_swap.get_obm());
Form1->StringGrid1->Cells[2][k*d/t+1]=IntToStr(arr_select.get_sr());
Form1->StringGrid2->Cells[2][k*d/t+1]=IntToStr(arr_select.get_obm());
Form1->StringGrid1->Cells[3][k*d/t+1]=IntToStr(arr_insert.get_sr());
Form1->StringGrid2->Cells[3][k*d/t+1]=IntToStr(arr_insert.get_obm());
Form1->StringGrid1->Cells[4][k*d/t+1]=IntToStr(arr_bubble.get_sr());
Form1->StringGrid2->Cells[4][k*d/t+1]=IntToStr(arr_bubble.get_obm());
Form1->StringGrid1->Cells[5][k*d/t+1]=IntToStr(arr_quick.get_sr());
Form1->StringGrid2->Cells[5][k*d/t+1]=IntToStr(arr_quick.get_obm());
}
current+=1;
ProgressBar1->Position=100*current/count;
}
sort->Enabled=false;
}
//---------------------------------------------------------------------------
AnsiString fn1="swap.bmp",fn2="select.bmp",fn3="insert.bmp",
fn4="bubble.bmp",fn5="quick.bmp";
void __fastcall TForm1::N2Click(TObject *Sender)
{
Form1->Image1->Picture->LoadFromFile(fn1);
Form1->Image2->Picture->LoadFromFile(fn2);
Form1->Image3->Picture->LoadFromFile(fn3);
Form1->Image4->Picture->LoadFromFile(fn4);
Form1->Image5->Picture->LoadFromFile(fn5);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N3Click(TObject *Sender)
{
Form1->Chart1->SaveToBitmapFile(fn1);
Form1->Chart2->SaveToBitmapFile(fn2);
Form1->Chart3->SaveToBitmapFile(fn3);
Form1->Chart4->SaveToBitmapFile(fn4);
Form1->Chart5->SaveToBitmapFile(fn5);
MessageBox(NULL,"Все графики выведены в файлы!","5 пар графиков!",MB_OK);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N1Click(TObject *Sender)
{
Form1->Chart1->SaveToBitmapFile(fn1);
MessageBox(NULL,"Графики (обменами) выведены в файл!","Сортировка обменами",MB_OK);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N4Click(TObject *Sender)
{
Form1->Image1->Picture->LoadFromFile(fn1);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N5Click(TObject *Sender)
{
Form1->Chart2->SaveToBitmapFile(fn2);
MessageBox(NULL,"Графики (выбором) выведены в файл!","Сортировка выбором",MB_OK);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N6Click(TObject *Sender)
{
Form1->Image2->Picture->LoadFromFile(fn2);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N7Click(TObject *Sender)
{
Form1->Chart3->SaveToBitmapFile(fn3);
MessageBox(NULL,"Графики (вставками) выведены в файл!","Сортировка вставками",MB_OK);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::N8Click(TObject *Sender)
{
Form1->Image3->Picture->LoadFromFile(fn3);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::N9Click(TObject *Sender)
{
Form1->Chart4->SaveToBitmapFile(fn4);
MessageBox(NULL,"Графики (пузырьком) выведены в файл!","Сортировка пузырьком",MB_OK);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::N10Click(TObject *Sender)
{
Form1->Image4->Picture->LoadFromFile(fn4);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::N11Click(TObject *Sender)
{
Form1->Chart5->SaveToBitmapFile(fn5);
MessageBox(NULL,"Графики (быстрая) выведены в файл!","Быстрая сортировка",MB_OK);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::N12Click(TObject *Sender)
{
Form1->Image5->Picture->LoadFromFile(fn5);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::helpClick(TObject *Sender)
{
MessageBox(NULL,"Разработаны в 2012 г. ","Рекурсивные функции для сортировки массивов",MB_OK);
}
//--------------------------------------------------------------------------
Это я сделал...

Второе задание:

6. Разработайте алгоритмы сортировок с помощью циклов (кроме быстрой сортировки) и напишите код для подраздела циклами с последующей отладкой и получением графически представляемых зависимостей, увеличив не менее чем на порядок размер сортируемых массивов и диапазон значений элементов массивов. Объясните полученные результаты.

Вот сдесь я и встал... Не знаю что делать! Кто поможет?
Если что файлы прикреплены. Посмотреть вложение Программа.rar
 

Вложения