Швидкі алгоритми сортування

          j--;

-42-

   m+=2;

        }

    } while (i<=j);

    }

    else

    {

    do {

      while (gret(index,mas,i,x))

           {

           i++;

           m++;

           }

      while (gret(index,mas,x,j))

           {

           j--;

           m++;

           }

      c++;

      if (i<=j)

        {

          c++;

          if (x==i)

              {

              x=j;

              m++;

              }

          else if (x==j)

              {

              x=i;

              m++;

              }

          swap(index, i, j);

          i++;

          j--;

          m+=2;

        };

    } while (i<j);

    }

    c++;

    if (i<r)

         index_qs(mas,index,i,r,asc);

    c++;

     if (l<j)

         index_qs(mas,index,l,j,asc);

  }

 

void DigitSort(int *mas, int len, bool asc=true)

{

int *index, *tmp;

index = new int[len+1];

int i;

for (i=1;i<=len;i++)

    index[i]=i;

m+=len;

index_qs(mas,index,1,len,asc);

-43-

tmp = new int[len+1];

for (i=1;i<=len;i++)

    tmp[i]=mas[index[i]];

m+=len;

for (i=1;i<=len;i++)

    mas[i]=tmp[i];

m+=len;

c+=len;

delete index;

delete tmp;

}

 

/////////////////////////////

 

int a[10000001];

int n;

 

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

 

void __fastcall TForm1::N4Click(TObject *Sender)

{

Form2->ShowModal();

if (Form2->ModalResult==mrOk)

   {

   int i;

   n=StrToInt(Form2->Edit1->Text);

   int da=StrToInt(Form2->Edit2->Text);

   int db=StrToInt(Form2->Edit3->Text)+1;

   Memo1->Clear();

   randomize();

   for (i=1;i<=n;i++)

      {

      a[i]=da+random(db-da);

      Memo1->Lines->Add(IntToStr(a[i]));

      }

   }

}

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

 

void __fastcall TForm1::N2Click(TObject *Sender)

{

if (OpenDialog1->Execute())

   {

   N5->Click();

   ifstream in_file(OpenDialog1->FileName.c_str());

   in_file>>n;

   int i;

   for (i=1;i<=n;i++)

       {

       in_file>>a[i];

       Memo1->Lines->Add(IntToStr(a[i]));

       }

   in_file.close();

   }

}

-44-

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

 

void __fastcall TForm1::N3Click(TObject *Sender)

{

if (SaveDialog1->Execute())

    {

    ofstream out_file(SaveDialog1->FileName.c_str());

    out_file<<Memo1->Lines->Count<<"\n";

    int i;

    for (i=0;i<Memo1->Lines->Count;i++)

        out_file<<Memo1->Lines->Strings[i].c_str()<<"\n";

    out_file.close();

    }

}

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

 

void __fastcall TForm1::N5Click(TObject *Sender)

{

Memo1->Clear();

Memo2->Clear();

Edit1->Text="";

n=0;

}

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

 

void __fastcall TForm1::N15Click(TObject *Sender)

{

int i;

bool asc;

n = Memo1->Lines->Count;

for (i=1;i<=n;i++)

    a[i]=StrToInt(Memo1->Lines->Strings[i-1]);

if (N12->Checked)

    asc=true;

if (N13->Checked)

    asc=false;

int t=GetTickCount();

if (n!=0)

{

if (N7->Checked)

    TreeSort(a,n,asc);

if (N8->Checked)

    HeapSort(a,n,asc);

if (N9->Checked)

    HoarSort(a,n,asc);

if (N10->Checked)

    DigitSort(a,n,asc);

}

Edit1->Text=IntToStr(GetTickCount()-t)+" ìñ";

Memo2->Clear();

for (i=1;i<=n;i++)

    Memo2->Lines->Add(IntToStr(a[i]));

}

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

 

-45-

void __fastcall TForm1::N17Click(TObject *Sender)

{

Close();       

}

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

 

void __fastcall TForm1::N16Click(TObject *Sender)

{

Form3->StringGrid1->Visible=true;

Form3->StringGrid1->Cells[0][1]="Ñîðòóâàííÿ  äåðåâîì";

Form3->StringGrid1->Cells[0][2]="ϳðàì³äàëüíå ñîðòóâàííÿ";

Form3->StringGrid1->Cells[0][3]="Ñîðòóâàííÿ  Õîàðà";

Form3->StringGrid1->Cells[0][4]="Ìåòîä öèôðîâîãî  øèôðóâàííÿ";

Form3->StringGrid1->Cells[1][0]="ʳëüê³ñòü  îïåðàö³é ïîð³âíÿííÿ";

Form3->StringGrid1->Cells[2][0]="ʳëüê³ñòü îïåðàö³é ïðèñâîºííÿ";

Form3->StringGrid1->Cells[3][0]="×àñ âèêîíàííÿ";

c=0;

m=0;

int i;

n = Memo1->Lines->Count;

Form3->Label1->Caption="ʳëüê³ñòü åëåìåíò³â  ìàñèâó - "+IntToStr(n);

for (i=1;i<=n;i++)

    a[i]=StrToInt(Memo1->Lines->Strings[i-1]);

int t=GetTickCount();

if (n!=0)

    TreeSort(a,n);

Form3->StringGrid1->Cells[3][1]=IntToStr(GetTickCount()-t)+" ìñ";

Form3->StringGrid1->Cells[1][1]=IntToStr(c);

Form3->StringGrid1->Cells[2][1]=IntToStr(m);

 

c=0;

m=0;

n = Memo1->Lines->Count;

for (i=1;i<=n;i++)

    a[i]=StrToInt(Memo1->Lines->Strings[i-1]);

t=GetTickCount();

if (n!=0)

   HeapSort(a,n);

Form3->StringGrid1->Cells[3][2]=IntToStr(GetTickCount()-t)+" ìñ";

Form3->StringGrid1->Cells[1][2]=IntToStr(c);

Form3->StringGrid1->Cells[2][2]=IntToStr(m);

 

c=0;

m=0;

n = Memo1->Lines->Count;

for (i=1;i<=n;i++)

    a[i]=StrToInt(Memo1->Lines->Strings[i-1]);

t=GetTickCount();

if (n!=0)

   HoarSort(a,n);

Form3->StringGrid1->Cells[3][3]=IntToStr(GetTickCount()-t)+" ìñ";

Form3->StringGrid1->Cells[1][3]=IntToStr(c);

Form3->StringGrid1->Cells[2][3]=IntToStr(m);

 

c=0;

-46-

m=0;

n = Memo1->Lines->Count;

for (i=1;i<=n;i++)

    a[i]=StrToInt(Memo1->Lines->Strings[i-1]);

t=GetTickCount();

if (n!=0)

   DigitSort(a,n);

Form3->StringGrid1->Cells[3][4]=IntToStr(GetTickCount()-t)+" ìñ";

Form3->StringGrid1->Cells[1][4]=IntToStr(c);

Form3->StringGrid1->Cells[2][4]=IntToStr(m);

Memo2->Clear();

for (i=1;i<=n;i++)

    Memo2->Lines->Add(IntToStr(a[i]));

Form3->ShowModal();

}

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

 

Unit2.h;

 

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

 

#ifndef Unit2H

#define Unit2H

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

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

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

class TForm2 : public TForm

{

__published: // IDE-managed Components

        TEdit *Edit1;

        TLabel *Label1;

        TButton *Button1;

        TButton *Button2;

        TLabel *Label2;

        TEdit *Edit2;

        TEdit *Edit3;

private: // User declarations

public:  // User declarations

        __fastcall TForm2(TComponent* Owner);

};

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

extern PACKAGE TForm2 *Form2;

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

#endif

 

Unit2.cpp

 

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

 

#include <vcl.h>

#pragma hdrstop

 

-47-

#include "Unit2.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm2 *Form2;

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

__fastcall TForm2::TForm2(TComponent* Owner)

        : TForm(Owner)

{

}

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

 

 

Unit3.h;

 

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

 

#ifndef Unit3H

#define Unit3H

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

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <Grids.hpp>

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

class TForm3 : public TForm

{

__published: // IDE-managed Components

        TStringGrid *StringGrid1;

        TButton *Button1;

        TLabel *Label1;

        void __fastcall Button1Click(TObject *Sender);

private: // User declarations

public:  // User declarations

        __fastcall TForm3(TComponent* Owner);

};

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

extern PACKAGE TForm3 *Form3;

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

#endif

 

Unit3.cpp;

 

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

 

#include <vcl.h>

#pragma hdrstop

 

#include "Unit3.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm3 *Form3;

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

-48-

__fastcall TForm3::TForm3(TComponent* Owner)

        : TForm(Owner)

{

}

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

 

void __fastcall TForm3::Button1Click(TObject *Sender)

{

Close();       

}