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

Автор: Пользователь скрыл имя, 02 Апреля 2013 в 22:09, курсовая работа

Описание работы

Розроблений програмне забезпечення працює у таких операційних системах (ОС) як: Windows /98/ME/NT/XP. Системними вимогами, за якими ПЗ працюватиме та буде видавати достовірні результати, можна вважати:
• процесори 6-го покоління (типу АМD, Pentium 300 МГц і вище);
• об’єм оперативної пам’яті 256 Мб. і вище

Содержание

ЗАВДАННЯ НА КУРСОВУ РОБОТУ…………………………………………...3
АНОТАЦІЯ...............................................................................................................5
ЗМІСТ........................................................................................................................6
ТЕОРЕТИЧНА ЧАСТИНА......................................................................................7
1.ТЕХНІЧНЕ ЗАВДАННЯ....................................................................................8
1.1. Підстави для розробки.................................................................................9
1.2. Призначення розробки.................................................................................9
1.3. Аналіз вимог до програмного забезпечення..............................................9
1.3.1. Функціональні вимоги.........................................................................9
1.3.2. Вимоги до складу та параметрів технічних засобів......................9
1.3.3. Вимоги до інтерфейсу.......................................................................10
1.3.4. Вимоги до інформаційної та програмної сумісності....................10
1.3.5. Вимоги до тестування програмного забезпечення........................10
1.4. Вимоги до програмної документації..........................................................10
1.4.1. Склад супровожжувальної документації.......................................10
1.4.2. вимоги до супроводжувальної документації...................................11
1.5. Стадії та етапи розробки..............................................................................11
1.6. Порядок контролю та приймання...............................................................11
ПРАКТИЧНА ЧАСТИНА.......................................................................................13
2. АРХІТЕКТУРА, ФУНКЦІОНУВАННЯ ТА ТЕХНІЧНІ ПОКАЗНИКИ…..14
2.1. Призначення та область застосування......................................................14
2.2. Опис та обгрунтування обраної архітектури............................................14
2.3. Опис алгоритму і функціонування програми.......................................... 15
2.3.1.Сортування деревом..........................................................................15
2.3.2. Пірамідальне сортування..................................................................18
2.3.3. Сортування Хоара..............................................................................19
2.3.4. Метод цифрового шифрування.........................................................20
2.4. Функціональна специфікація......................................................................21
2.4.1. Опис фунціональних можливостей..................................................21
2.4.2. Опис інтерфейсу користувач...........................................................22
-7-
2.4.3. Діаграма прецедентів різних режимів роботи..............................23
2.5. Технічна специфікація................................................................................23
2.5.1. Опис діаграми модулів......................................................................23
2.5.2. Опис та обгрунтування вхідних та вихідних даних......................24
3. КОНСТРУЮВАННЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ...........................25
3.1. Опис та обгрунтування обраних програмних засобів..............................25
3.2. Опис програми.............................................................................................25
4. ПРОГРАМА ТА МЕТОДИКА ВИПРОБУВАНЬ............................................30
4.1. Об’єкт випробувань.....................................................................................30
4.2. Використані технічні засоби......................................................................30
4.3. Порядок та методика випробувань............................................................30
4.4. Результати випробувань.............................................. ...............................31
5. ВИСНОВКИ........................................................................................................33
6. ВИКОРИСТАНА ЛІТЕРАТУРА......................................................................34
7. ДОДАТКИ...........................................................................................................35
Додаток А. Код програми..................................................................................35

Работа содержит 1 файл

Текст курсової.doc

— 493.00 Кб (Скачать)

          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();       

}


Информация о работе Швидкі алгоритми сортування