Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
deadceasar
1

Системный анализ алгоритмов сортировки

28.04.2010, 16:17. Просмотров 1151. Ответов 0
Метки нет (Все метки)

В чем суть.
Надо исследовать 3 алгоритма сортировки : Быстрой сортировки, Пирамидальной сортировки, Сортировки слиянием. Исследовать более углубленно, по показателям.

//Количество операций сравнение ключей
//Количество операций присваивания ключей
//Количество операций сравнения индексов
//Количество операций присваивания индексов
//количество операций инкремента , декремента индексов
//количество индексирований

Но надо не усложнять уже имеющиеся алгоритмы, а создать свою систему кассов
Index
Key
Array

и перегрузить все необходимые операции.
Сделать надо ввиде приложения.

У меня на это тяму нехватает, дело в том, что я вообще программистом не являюсь я связист и техник.
Надеюсь, что может кто нибуть сможет решит задачу.

Люди добрые выручайте, вам опыт будет!

Добавлено через 21 минуту
За основу можно взять вот этот кодинг, тут похожая задача решается.
ПРИЛОЖЕНИЕ 1
Программный код основной формы
Приложение 1.1
Заголовочный файл (main.h)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
   
 //-------------------------------------------------------------------------
 #ifndef mainH
 #define mainH
 //-------------------------------------------------------------------------
 #include <Classes.hpp>
 #include <Controls.hpp>
 #include <StdCtrls.hpp>
 #include <Forms.hpp>
  #include <ExtCtrls.hpp>
  #include "uclass.h"
  //------------------------------------------------------------------------
  typedef void (*SortPtr) (Array&);
  typedef
  struct data
  {
   SortPtr F;
   Array mm;
   HINSTANCE Lib;
  } data;
  class TMainFrm : public TForm
  {
  __published:  // IDE-managed Components
          TComboBox *ArrayCmb;
          TComboBox *SortCmb;
          TButton *StartBtn;
          TLabel *SortLbl;
          TLabel *ArrayLbl;
          TPaintBox *SortPbx;
          TLabeledEdit *DelayLbe;
          TLabeledEdit *SizeLbe;
          TButton *StatBtn;
          TButton *StopBtn;
          void __fastcall FormCreate(TObject *Sender);
          void __fastcall StatBtnClick(TObject *Sender);
          void __fastcall StartBtnClick(TObject *Sender);
          void __fastcall StopBtnClick(TObject *Sender);
          void __fastcall FormClose(TObject *Sender, TCloseAction &Action);
  private:  // User declarations
          HINSTANCE Lib;
          HANDLE hThread;
          Drawer* Dr;
 
  public:       // User declarations
          __fastcall TMainFrm(TComponent* Owner);
          void __fastcall EnBtn();
 
  };
 
  DWORD WINAPI Start(LPVOID);
  //------------------------------------------------------------------------
  extern PACKAGE TMainFrm *MainFrm;
  //------------------------------------------------------------------------
  #endif
Приложение 1.2
Файл реализации (main.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 #include <vcl.h>
 #include <math.h>
 #include <stdlib.h>
 #include "cmp.h"
 #pragma hdrstop
 #include "uclass.h"
 #include "main.h"
 #include "arrays.h"
 //-------------------------------------------------------------------------
  #pragma package(smart_init)
  #pragma resource "*.dfm"
  TMainFrm *MainFrm;
 
  //-----------------------------------------------------------------------
  __fastcall TMainFrm::TMainFrm(TComponent* Owner)
          : TForm(Owner)
  {
 
  }
  //------------------------------------------------------------------------
 
  void __fastcall TMainFrm::FormCreate(TObject *Sender)
  {
   Dr = new Drawer;
   Dr->Set(SortPbx->Canvas, 0,0,400,500,1);
  }
  //-----------------------------------------------------------------------
 
  struct data  dwThrdParam;
  DWORD WINAPI Start(void* Dt)
  {
   data *D = (data*)(Dt);
   if (D->F) D->F(D->mm);
   if (D->Lib) FreeLibrary(D->Lib);
   MainFrm->SortPbx->Canvas->Unlock();
   MainFrm->EnBtn();
   return 0;
  }
  //-----------------------------------------------------------------------
 
  void __fastcall TMainFrm::StatBtnClick(TObject *Sender)
  {
  StatFrm->Show();
  }
  //-----------------------------------------------------------------------
  void __fastcall TMainFrm::EnBtn()
  {
   StatBtn->Enabled = true;
   StartBtn->Enabled = true;
   StopBtn->Enabled=false;
   ArrayCmb->Enabled = true;
   SortCmb->Enabled = true;
   DelayLbe->Enabled = true;
   SizeLbe->Enabled = true;
  }
 
  void __fastcall TMainFrm::StartBtnClick(TObject *Sender)
  {
  if (ArrayCmb->ItemIndex==-1){ShowMessage("Óêàæèòå ñïîñîá çàïîëíåíèÿ ìàññèâà!");return;}
 if (SortCmb->ItemIndex==-1){ShowMessage("Óêàæèòå òèï ñîðòèðîâêè!");return;}
 if(StrToInt(DelayLbe->Text)<0){ShowMessage("Âðåìåííàÿ çàäåðæêà íå ìîæåò áûòü <0!");return;}
 if(StrToInt(SizeLbe->Text)<=0){ShowMessage("Ðàçìåð ìàññèâà äîëæåí áûòü>0!");return;}
   if (Lib) FreeLibrary(Lib);
   int* m;
  int size = StrToInt(SizeLbe->Text);
  TPen *P = new TPen;
  P->Color = clBtnFace;
  SortPbx->Canvas->Pen = P;
  SortPbx->Canvas->Rectangle(0,0,SortPbx->Width,SortPbx->Height);
 
   StatBtn->Enabled = false;
   StopBtn->Enabled=true;
   StartBtn->Enabled = false;
   ArrayCmb->Enabled = false;
   SortCmb->Enabled = false;
   DelayLbe->Enabled = false;
   SizeLbe->Enabled = false;
   switch(ArrayCmb->ItemIndex)
   {
 
    case 0:
          { m = RightOrder(size);break; }
    case 1:
          { m = ReverseOrder(size);break; }
    case 2:
          { m = Random(size);break; }
    case 3:
          { m = GaussianDist(size);break; }
    default: return;
   }
  switch(SortCmb->ItemIndex)
   {
    case 0:
          {
           Lib = LoadLibrary("insertsort.dll");
           break;
          }
    case 1:
          {
            Lib = LoadLibrary("selectionsort.dll");
            break;
           }
     case 2:
           {
            Lib = LoadLibrary("probubble.dll");
            break;
           }
     case 3:
           {
            Lib = LoadLibrary("Quick.dll");
            break;
           }
     case 4:
           {
            Lib = LoadLibrary("Shall.dll");
            break;
           }
     case 5:
           {
            Lib = LoadLibrary("Merge.dll");
            break;
           }
     default: return;
    }
    Dr->ChangeDelay(StrToInt(DelayLbe->Text));
    Array M(m,size,Dr);
     delete [] m;
    if (Lib)
    {
     SortPtr Func =
       (SortPtr) GetProcAddress(Lib,"_Sort");
     if (Func)
     {
    dwThrdParam.Lib = Lib;
    dwThrdParam.F = Func;
    dwThrdParam.mm = M;
    DWORD dwThreadId;
    SortPbx->Canvas->Lock();
    hThread = CreateThread(NULL,0,Start,&dwThrdParam,0,&dwThreadId);
     }
    }
   }
   //-----------------------------------------------------------------------
 
   void __fastcall TMainFrm::StopBtnClick(TObject *Sender)
   {
   TerminateThread(hThread,NULL);
   SortPbx->Canvas->Unlock();
   if (Lib) FreeLibrary(Lib);
   EnBtn();
   StopBtn->Enabled=false;
   TPen *P = new TPen;
   P->Color = clBtnFace;
   SortPbx->Canvas->Pen = P;
   SortPbx->Canvas->Rectangle(0,0,SortPbx->Width,SortPbx->Height);
   }
   //-----------------------------------------------------------------------
 
   void __fastcall TMainFrm::FormClose(TObject *Sender, TCloseAction &Action)
   {
    if (hThread) TerminateThread(hThread,NULL);
    if (Lib) FreeLibrary(Lib);
   }
ПРИЛОЖЕНИЕ 2
Программный код формы «Статистика»
Приложение 2.1
Заголовочный файл (cmp.h)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 #ifndef cmpH
 #define cmpH
 //-------------------------------------------------------------------------
 #include <Classes.hpp>
 #include <Controls.hpp>
 #include <StdCtrls.hpp>
 #include <Forms.hpp>
 #include <DBGrids.hpp>
 #include <Grids.hpp>
  #include <ComCtrls.hpp>
  #include <Stdio.h>
  #include "uclass.h"
  #include <Dialogs.hpp>
  //------------------------------------------------------------------------
  class TStatFrm : public TForm
  {
  __published:  // IDE-managed Components
          TLabel *SortLbl;
          TCheckBox *InsertChb;
          TCheckBox *SelectChb;
          TCheckBox *BubbleChb;
          TCheckBox *QuickChb;
          TCheckBox *ShellChb;
          TCheckBox *MergChb;
          TLabel *CondLbl;
          TRadioButton *NumRbt;
          TRadioButton *IterRbt;
          TRadioButton *TypeRbt;
          TStringGrid *CompStg;
          TButton *SaveBtn;
          TButton *MakeBtn;
          TEdit *NumEdt;
          TEdit *IterEdt;
          TComboBox *TypeCmb;
          TSaveDialog *SaveDlg;
          void __fastcall NumRbtClick(TObject *Sender);
          void __fastcall IterRbtClick(TObject *Sender);
          void __fastcall TypeRbtClick(TObject *Sender);
          void __fastcall FormCreate(TObject *Sender);
          void __fastcall MakeBtnClick(TObject *Sender);
          void __fastcall SaveBtnClick(TObject *Sender);
  private:  // User declarations
          HINSTANCE Lib;
          typedef void(*SortPtr) (Array&);
          typedef char* (*SortTypePtr) ();
          int Pos;
  public:       // User declarations
          __fastcall TStatFrm(TComponent* Owner);
          void __fastcall Statistic(int , int, int , int);
          FILE *dF;
  };
  //------------------------------------------------------------------------
  extern PACKAGE TStatFrm *StatFrm;
  //------------------------------------------------------------------------
  #endif
Приложение 2.2
Файл реализации (cmp.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <vcl.h>
#pragma hdrstop
#include "cmp.h"
#include "uclass.h"
#include "arrays.h"
//------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
 
 #define NCount 1000
 #define Niter 100
 
 TStatFrm *StatFrm;
 //------------------------------------------------------------------------
 __fastcall TStatFrm::TStatFrm(TComponent* Owner)
         : TForm(Owner)
 {
 }
 //------------------------------------------------------------------------
 void __fastcall TStatFrm::NumRbtClick(TObject *Sender)
 {
 NumEdt->Enabled = true;
 NumEdt->Text = "0";
 IterEdt->Enabled = false;
 IterEdt->Text = "100";
 TypeCmb->Enabled = false;
 TypeCmb->Text="Ïî ðàâíîìåðíîìó çàêîíó";
 }
 //------------------------------------------------------------------------
 void __fastcall TStatFrm::IterRbtClick(TObject *Sender)
 {
 IterEdt->Enabled = true;
 IterEdt->Text = "0";
 NumEdt->Enabled = false;
 NumEdt->Text ="1000";
 TypeCmb->Enabled = false;
 TypeCmb->Text=" Ïî ðàâíîìåðíîìó çàêîíó ";
 }
 //---------------------------------------------------------------------
 void __fastcall TStatFrm::TypeRbtClick(TObject *Sender)
 {
 TypeCmb->Enabled = true;
 TypeCmb->Text = "Âûáðàòü èç ñïèñêà";
 NumEdt->Enabled = false;
 NumEdt->Text = "1000";
 IterEdt->Enabled = false;
 IterEdt->Text = "100";
 }
 //---------------------------------------------------------------------
 void __fastcall TStatFrm::FormCreate(TObject *Sender)
 {
 CompStg->Cells[0][0] = "Òèï ñîðòèðîâêè";
 CompStg->Cells[1][0] = "Îïåð. ñðàâíåíèÿ";
 CompStg->Cells[2][0] = "Îïåð. ñðàâíåíèÿ";
 CompStg->Cells[3][0] = "Âðåìÿ";
 }
 //---------------------------------------------------------------------
 void __fastcall TStatFrm::MakeBtnClick(TObject *Sender)
 {
 Pos = 1;
 int* m;
 int iterat,size;
 int TypeArray;
 if (NumRbt->Checked)
  {
   size = StrToInt(NumEdt->Text);
   TypeArray = 2;
   iterat = Niter;
  }
  else if (IterRbt->Checked)
   {
    iterat = StrToInt(IterEdt->Text);
    size = NCount;
    TypeArray = 2;
   }
   else if (TypeRbt->Checked)
    {
         switch(TypeArray = TypeCmb->ItemIndex)
         {
          case 0:             {iterat = 1; break; }
          case 1:             {iterat = 1; break; }
          case 2:             {iterat = Niter; break; }
          case 3:             {iterat = Niter; break; }
         }
       size = NCount;
    }
    if (InsertChb->Checked) { Statistic(0,TypeArray, iterat, size);  Pos++;}
    if (SelectChb->Checked) {Statistic(1,TypeArray, iterat, size);   Pos++;}
    if (BubbleChb->Checked) {Statistic(2,TypeArray, iterat, size);   Pos++;}
    if (QuickChb->Checked) { Statistic(3,TypeArray, iterat, size);    Pos++;}
    if (ShellChb->Checked) {Statistic(4,TypeArray, iterat, size);    Pos++;}
    if (MergChb->Checked) {Statistic(5,TypeArray, iterat, size);    Pos++;}
 }
 void __fastcall TStatFrm::Statistic(int TypeSort, int TypeArray, int iterat,int size)
 {
 SYSTEMTIME st1,st2;
 int * mas;
 if (Lib) FreeLibrary(Lib);
  switch(TypeSort)
   {
    case 0:        {Lib = LoadLibrary("insertsort.dll"); break; }
    case 1:        {Lib = LoadLibrary("selectionsort.dll"); break; }
    case 2:        { Lib = LoadLibrary("probubble.dll"); break; }
    case 3:        {Lib = LoadLibrary("Quick.dll"); break; }
    case 4:        {Lib = LoadLibrary("Shall.dll"); break; }
    case 5:        {Lib = LoadLibrary("Merge.dll"); break; }
    default: return;
   }
    SortPtr Func;
   SortTypePtr SortTypeFunc;
   if (Lib)
   {
    Func = (SortPtr) GetProcAddress(Lib,"_Sort");
    SortTypeFunc = (SortTypePtr) GetProcAddress(Lib,"_TypeSort");
    if (!Func || !SortTypeFunc) return;
   }
   long avgTime = 0;
   long avgOCmp = 0;
   long avgOEql = 0;
   int i;
   for (i = 0; i < iterat; i++)
    {
           switch(TypeArray)
          {
           case 0:
                  { mas = RightOrder(size);break; }
           case 1:
                  { mas = ReverseOrder(size);break; }
           case 2:
                  { mas = Random(size);break; }
           case 3:
                  { mas = GaussianDist(size);break; }
          }
     Array m(mas,size,0);
     GetLocalTime(&st1);
     Func(m);
     GetLocalTime(&st2);
     avgOEql += m.GetEql();
     avgOCmp += m.GetCompare();
     avgTime +=
     (st2.wMinute-st1.wMinute) * 60000 + (st2.wSecond - st1.wSecond) * 1000+
          (st2.wMilliseconds - st1.wMilliseconds);
     delete [] mas;
    }
    avgTime /= iterat;
    avgOCmp /= iterat;
    avgOEql /= iterat;
    CompStg->Cells[0][Pos] = SortTypeFunc();
    CompStg->Cells[1][Pos] = IntToStr(avgOCmp);
    CompStg->Cells[2][Pos] = IntToStr(avgOEql);
    CompStg->Cells[3][Pos] = IntToStr(avgTime);
    FreeLibrary(Lib);
  }
  //-----------------------------------------------------------------------
  void __fastcall TStatFrm::SaveBtnClick(TObject *Sender)
  {
   SaveDlg->DefaultExt="txt";
   if (SaveDlg->Execute())
    {
     dF = fopen(SaveDlg->FileName.c_str(),"w");
     fprintf(dF,"%25s %20s %23s %10s\n",
             "Ñîðòèðîâêà", "Îïåð.ñðàâíåíèÿ", "Îïåð.ïðèñâàèâàíèÿ", "Âðåìÿ");
     for (int i=1; i<(Pos);i++)
      {
       fprintf(dF,"%25s %20s %23s %10s\n",
                  CompStg->Cells[0][i].c_str(),
                  CompStg->Cells[1][i].c_str(),
                  CompStg->Cells[2][i].c_str(),
                  CompStg->Cells[3][i].c_str());
       }
       fprintf(dF,"\n");
     fclose(dF);
    }
  }
//ПРИЛОЖЕНИЕ 3
//Программный код модуля uclass
//Приложение 3.1
//Заголовочный файл (uclass.h)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 #ifndef uclassH
 #define uclassH
 #include <vcl.h>
 class Array;
 class Item
 {
  int value;
  int index;
  Array * Owner;
   public:
          Item(){value = 0; Owner = 0;}
          Item & operator = (const Item & src);
          bool operator < (const Item & src);
          bool operator > (const Item & src);
          bool operator <= (const Item & src);
          bool operator >= (const Item & src);
          bool operator == (const Item & src);
          bool operator != (const Item & src);
          void SetOwner(Array * a) {Owner = a;}
          void SetValue(int v) {value = v; }
          void SetIndex(int i) {index = i;}
          int Value() {return value;}
          int Index(){return index;}
          friend class Array;
  };
 
  class Drawer
  {
   int left;
  int top;
  int bottom;   //height
  int right;  //weight
  TCanvas* Canvas;
  int delay;
  public:
          void Set(TCanvas* Cnv,int l,int t,int b,int r,int d) {Canvas=Cnv; left=l; top=t; bottom=b; right=r; delay=d;}
          int Left() {return left;}
          int Top() {return top;}
          int Bottom() {return bottom;}
          int Right() {return right;}
          int Delay() {return delay;}
    Drawer() {left = top = bottom = right = delay = 0; Canvas = NULL;}
          void ChangeDelay(int d) {delay = d;}
          void Draw(int,int);
          void Erase(int,int);
  };
 
  class Array
  {
   Item * Items;
   int len;
   Drawer *drw;
   int min;
   int max;
   long Compare;
   long Eql;
   public:
          int Length() {return len;}
          Array(int* , int, Drawer*);
          Array() {len = min = max = Eql = Compare = 0;}
          Array(int);
          Array(const Array&);
          void DrawPoint(const Item&, const Item&);
          Item & operator [] (int i){if (i >= 0 && i < len) return Items[i];}
          Array operator = (const Array& m);
          ~Array(){if(Items) delete [] Items;}
          void SetDrawer(Drawer* d);
          long GetCompare () {return Compare;}
          long GetEql() {return Eql;}
          void IncCompare () {Compare++;}
          void IncEql () {Eql++;}
          void ClearParam() {Compare = Eql = 0;}
  };
  //------------------------------------------------------------------------
  #endif
Приложение 3.2
Файл реализации (uclass.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#pragma hdrstop
#include "uclass.h"
//-------------------------------------------------------------------------
#pragma package(smart_init)
Item & Item::operator = (const Item & src)
 {
   if (Owner)
      {
      Owner->DrawPoint(*this, src); Owner->IncEql();
       }
    if(this != &src) value = src.value;
    return *this;
  }
 bool Item::operator < (const Item & src)
 {Owner->IncCompare(); return value < src.value;}
 
 bool Item::operator > (const Item & src)
 {Owner->IncCompare(); return value > src.value;}
 
 bool Item::operator <= (const Item & src)
 {Owner->IncCompare(); return value <= src.value;}
 
 bool Item::operator >= (const Item & src)
 {Owner->IncCompare(); return value >= src.value;}
 
 bool Item::operator == (const Item & src)
 {Owner->IncCompare(); return value == src.value;}
 
 bool Item::operator != (const Item & src)
 {Owner->IncCompare(); return value != src.value;}
 
 void Drawer::Draw(int x, int y)
 {
  if (Canvas)
   Canvas->Pixels[x][y] = clBlack;
 }
 
 void Drawer::Erase(int x,int y)
 {
  if (Canvas)
   Canvas->Pixels[x][y] = clBtnFace;
 }
 
 void Array::DrawPoint(const Item& I1, const Item& I2)
 {
  double x,y;
  if (drw){
  x = drw->Right() * I1.index / len ;
  y = drw->Bottom() - drw->Bottom() * I1.value / (max - min);
  drw->Erase(x,y);
  y = drw->Bottom() - drw->Bottom() * I2.value / (max - min);
  drw->Draw(x,y);
  Sleep(drw->Delay());}
 }
 
 Array::Array(int* mas, int n, Drawer* Dr)
 {
  Items = new Item[n];
  int i;
  min = max = mas[0];
  drw = Dr;
  len = n;
  double x,y;
   for (i = 0; i < n; i++)
  {
   if (mas[i] > max) max = mas[i];
   if (mas[i] < min) min = mas[i];
  }                   
 
  for (i = 0; i < n; i++)
  {
   Items[i].value = mas[i];
   Items[i].index = i;
   Items[i].Owner = this;
 
   if (drw)
   {
    x = drw->Right() * i / len ;
    y = drw->Bottom() - drw->Bottom() * mas[i] / (max - min);
    drw->Draw(x,y);
   }
  }
  Eql = Compare = 0;
 }
 
 Array::Array(int n)
 {
  Items = new Item[n];
  int i;
  min = max = Items[0].value;
  drw = 0;
  len = n;
  double x,y;
  for (i = 0; i < n; i++)
  {
   Items[i].index = i;
   Items[i].Owner = this;
  }
  Eql = Compare = 0;
  }
  
  void Array::SetDrawer(Drawer* d)
  {
   drw = d;
   double x,y;
    for (int i = 0; i < len; i++)
    {
     x = drw->Right() * i / len ;
     y = drw->Bottom() - drw->Bottom() * operator[](i).value / (max - min);
     drw->Draw(x,y);
    }
  }
  
  Array Array::operator = (const Array& m)
  {
   len = m.len;
   drw = m.drw;
   Eql = m.Eql;
   Compare = m.Compare;
   Items = new Item[len];
   int i;
   double x,y;
   min = m.min;
   max = m.max;
   for (i = 0; i < m.len; i++)
   {
    Items[i].index = m.Items[i].index;
    Items[i].value = m.Items[i].value;
    Items[i].Owner = this;
      if (drw)
    {
     x = drw->Right() * i / len ;
     y = drw->Bottom() - drw->Bottom() * Items[i].value / (max - min);
     drw->Draw(x,y);
    }
   }
   return *this;
  }
  
  Array::Array(const Array& m)
  {
   len = m.len;
   drw = m.drw;
   Items = new Item[len];
   int i;
   double x,y;
   min = m.min;
   max = m.max;
   Eql = Compare = 0;
   for (i = 0; i < m.len; i++)
   {
    Items[i].index = m.Items[i].index;
    Items[i].value = m.Items[i].value;
    Items[i].Owner = this;
      if (drw)
    {
     x = drw->Right() * i / len ;
     y = drw->Bottom() - drw->Bottom() * Items[i].value / (max - min);
     drw->Draw(x,y);
    }
   }  
  }
ПРИЛОЖЕНИЕ 4
Программный код библиотек
Приложение 4.1
Заголовочный файл (head.h) (общий для всех библиотек)
C++
1
2
3
4
5
6
7
8
  #ifdef BUILDING_DLL
  #define DLL_EXP __declspec(dllexport)
  #else
  #define DLL_EXP __declspec(dllimport)
  #endif
   
   extern "C" DLL_EXP void Sort(Array&);
   extern "C" DLL_EXP char* TypeSort();
Приложение 4.2
Файл реализации алгоритма быстрой сортировки (Uquick.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 #include <windows.h>
 #include "uclass.h"
 #include "head.h"
 //-------------------------------------------------------------------------
 //   Important note about DLL memory management when your DLL uses the
 //   static version of the RunTime Library:
 //
 //   If your DLL exports any functions that pass String objects (or structs/
 //   classes containing nested Strings) as parameter or function results,
  //   you will need to add the library MEMMGR.LIB to both the DLL project and
  //   any other projects that use the DLL.  You will also need to use MEMMGR.LIB
  //   if any other projects which use the DLL will be performing new or delete
  //   operations on any non-TObject-derived classes which are exported from the
  //  DLL. Adding MEMMGR.LIB to your project will change the DLL and its calling
  //   EXE's to use the BORLNDMM.DLL as their memory manager.  In these cases,
  //   the file BORLNDMM.DLL should be deployed along with your DLL.
  //
  //   To avoid using BORLNDMM.DLL, pass string information using "char *" or
  //   ShortString parameters.
  //
  //   If your DLL uses the dynamic version of the RTL, you do not need to
  //   explicitly add MEMMGR.LIB as this will be done implicitly for you
  //------------------------------------------------------------------------
 
     int partition (Array& m, int a, int b)
      {
        int i = a;
        Item tmp;
        for (int j = a; j <= b; j++)
         {
           if (m[j] <= m[b])
            {
              tmp = m[i];
              m[i] = m[j];
              m[j] = tmp;
              i++;
            }
         }
        return i-1;
      }
 
     void quicksort (Array& m, int a, int b)
      {
       if (a >= b) return;
       int c = partition (m, a, b);
       quicksort (m, a, c-1);
       quicksort (m, c+1, b);
      }
 
     extern "C" void Sort(Array& m)
     {
      quicksort(m, 0, m.Length() - 1);
     }
 
     extern "C" char* TypeSort()
     { return "Áûñòðàÿ ñîðòèðîâêà";}
 
  #pragma argsused
  int WINAPI DllEntryPoint(HINSTANCE hinst, unsigned long reason, void* lpReserved)
  {
          return 1;
  }
Приложение 4.3
Файл реализации алгоритма сортировки вставками (Uinsert.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 #include <windows.h>
 #include "uclass.h"
 #include "head.h"
 
   extern "C" void Sort(Array& m)
   {
       int i, j;
       Item value;
       for (i = 1; i < m.Length(); i++)
        {
            value = m[i];
            for (j = i-1; (j >= 0) && (m[j] > value); j--)
            {
                m[j+1] = m[j];
            }
            m[j+1] = value;
        }
    }
 
    extern "C" char* TypeSort()
    { return "Ñîðòèðîâêà âñòàâêàìè";}
 
  #pragma argsused
  int WINAPI DllEntryPoint(HINSTANCE hinst, unsigned long reason, void* lpReserved)
  {
          return 1;
  }
Приложение 4.4
Файл реализации алгоритма сортировки выбором (USelect.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 #include <windows.h>
 #include "uclass.h"
 #include "head.h"
 
 extern "C" void Sort( Array& m )
 {
  int i,j, min;
  Item tmp;
  int len = m.Length();
      for(i = 0; i < len - 1; i++)
      {
    min = i;
    for(j = i + 1; j < len; j++)
        if( m[min] > m[j]) min = j;
    tmp = m[i];
    m[i] = m[min];
    m[min] = tmp;
      }
  }
 
  extern "C" char* TypeSort()
  { return "Ñîðòèðîâêà âûáîðîì"; }
 
  #pragma argsused
  int WINAPI DllEntryPoint(HINSTANCE hinst, unsigned long reason, void* lpReserved)
  {
          return 1;
  }
Приложение 4.5
Файл реализации алгоритма сортировки пузырьком (Ububble.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 #include <windows.h>
 #include "uclass.h"
 #include "head.h"
 
 extern "C" void Sort(Array& a)
 {
  int i, j;
  Item tmp;
     for(i = a.Length() - 1 ; i > 0 ; i--)
          for(j = 0 ; j < i ; j++)
        if( a[j] > a[j+1] )
        {
        tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        }
  }
 
  extern "C" char* TypeSort()
  { return "Ñîðòèðîâêà ïóçûðüêîì"; }
  #pragma argsused
  int WINAPI DllEntryPoint(HINSTANCE hinst, unsigned long reason, void* lpReserved)
  {
          return 1;
  }
Приложение 4.6
Файл реализации алгоритма сортировки слиянием (Umerge.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 #include <windows.h>
 #include "uclass.h"
 #include "head.h"
 
 void merge(Array& m, int lb, int split, int ub)
 {
 // Ñëèÿíèå óïîðÿäî÷åííûõ ÷àñòåé ìàññèâà â áóôåð temp
 // ñ äàëüíåéøèì ïåðåíîñîì ñîäåðæèìîãî temp a^ a[lb]...a[ub]
 
  // òåêóùàÿ ïîçèöèÿ ÷òåíèÿ èç ïåðâîé ïîñëåäîâàòåëüíîñòè a[lb]...a[split]
    long pos1=lb;
 
    // òåêóùàÿ ïîçèöèÿ ÷òåíèÿ èç âòîðîé ïîñëåäîâàòåëüíîñòè a[split+1]...a[ub]
    long pos2=split+1;
 
    // òåêóùàÿ ïîçèöèÿ çàïèñè â temp
    long pos3=0;
 
    Array temp(ub - lb + 1);
 
    // èäåò ñëèÿíèå, ïîêà åñòü õîòü îäèí ýëåìåíò â êàæäîé ïîñëåäîâàòåëüíîñòè
    while (pos1 <= split && pos2 <= ub) {
      if (m[pos1] < m[pos2])
        temp[pos3++] = m[pos1++];
      else
        temp[pos3++] = m[pos2++];
    }
 
    // îäíà ïîñëåäîâàòåëüíîñòü çàêîí÷èëàñü -
    // êîïèðîâàòü îñòàòîê äðóãîé â êîíåö áóôåðà
    while (pos2 <= ub)   // ïîêà âòîðàÿ ïîñëåäîâàòåëüíîñòü íå ïóñòà
      temp[pos3++] = m[pos2++];
    while (pos1 <= split)  // ïîêà ïåðâàÿ ïîñëåäîâàòåëüíîñòü íå ïóñòà
      temp[pos3++] = m[pos1++];
 
    // ñêîïèðîâàòü áóôåð temp â a[lb]...a[ub]
    for (pos3 = 0; pos3 < ub-lb+1; pos3++)
      m[lb+pos3] = temp[pos3];
  }
 
  void mergeSort(Array& m, int lb, int ub) {
    int split;                   // èíäåêñ, ïî êîòîðîìó äåëèì ìàññèâ
    if (lb < ub) {                // åñëè åñòü áîëåå 1 ýëåìåíòà
 
      split = (lb + ub) / 2;
 
      mergeSort(m, lb, split);       // ñîðòèðîâàòü ëåâóþ ïîëîâèíó
      mergeSort(m, split+1, ub);// ñîðòèðîâàòü ïðàâóþ ïîëîâèíó
      merge(m, lb, split, ub);    // ñëèòü ðåçóëüòàòû â îáùèé ìàññèâ
    }
  }
 
  extern "C" void Sort(Array& m)
  {
   mergeSort(m,0, m.Length() - 1);
  }
 
  extern "C" char* TypeSort() {return "Ñîðòèðîâêà ñëèÿíèåì"; }
  #pragma argsused
  int WINAPI DllEntryPoint(HINSTANCE hinst, unsigned long reason,void* lpReserved)
  {
          return 1;
  }
Приложение 4.7
Файл реализации алгоритма сортировки Шелла (UShall.cpp)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 #include <windows.h>
 #include "uclass.h"
 #include "head.h"
 
  extern "C" void Sort(Array& m)
         {
             int j;
             int len = m.Length();
             int step = len / 2;
              Item tmp;
              while (step > 0)
              {
                  for (int i = 0; i < (len - step); i++)
                  {
                      j = i;
                      while ((j >= 0) && (m[j] > m[j + step]))
                      {
                          tmp = m[j];
                          m[j] = m[j + step];
                          m[j + step] = tmp;
                          j--;
                      }
                  }
                  step /= 2;
              }
          }
 
   extern "C" char* TypeSort() {return "Ñîðòèðîâêà Øåëëà";}
 
  #pragma argsused
  int WINAPI DllEntryPoint(HINSTANCE hinst, unsigned long reason, void* lpReserved)
  {
          return 1;
  }
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.04.2010, 16:17
Ответы с готовыми решениями:

Анализ алгоритмов сортировки
Доброго времени суток . На кануне меня попросили реализовать программу для анализа двух алгоритмов...

Сравнительный анализ алгоритмов сортировки
Помогите пожалуйста реализовать программу для сравнения алгоритмов сортировок. Нужно отдельно...

Анализ алгоритмов
почему для этого примера: tmp = a; a = b; b = tmp; О-нотация равна O(1), а не O(3) или для...

Асимптотический анализ алгоритмов
Здравствуйте. Помогите разобраться, что такое асимптотический анализ алгоритмов. Я мало что помню...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.04.2010, 16:17

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Анализ сложности алгоритмов в с++
Напишите программы, реализующие алгоритм обменной сортировки методом пузырька и алгоритм сортировки...

Анализ алгоритмов поиска
Написать программу, в которой используются четыре метода поиска: 1. Линейный поиск в массиве....

5 алгоритмов сортировки
Ребят,помогите с курсовой по программированию,пожалуйста.Нужно создать матрицу(с помощью...

Иследование алгоритмов сортировки
дан одномерный массив. Сформировать новый массив, отрицательные элементы которого отсортированы по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.