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

При виборі пункту меню “Відкрити з файлу” перед користувачем з’являється діалогове вікно, в якому користувач може вибрати файл, з якого буде прочитано вхідний масив:

Рис. 3.3. Читання даних з файлу

При виборі пункту меню “Згенерувати випадково” перед користувачем з’являється вікно, в якому він може задати кількість елементів масиву та діапазон елементів. Після натиснення на кнопку “Згенерувати” програма згенерує випадковим чином задану кількість елементів із заданого діапазону:

-27-

 

Рис. 3.4. Задання даних випадковим чином

Користувач може вибрати  один із методів сортування: сортування деревом, пірамідальне сортування, сортування Хоара чи метод цифрового шифрування. Це він може зробити вибравши пункт меню “Метод сортування”:

 

Рис. 3.5. Вибір методу сортування

При виборі пункту меню “Тип сортування” користувач може вибрати спосіб сортування: за заростанням чи за спаданням:

Рис. 3.6. Вибір способу сортування

Користувач може виконати наступні дії (вибравши пункт меню “Дії”): відсортувати заданий масив, порівняти методи сортування для заданого масиву, закрити програму:

 

 

 

-28-

Рис. 3.7. Вибір дії

При виборі пункту меню “Відсортувати” заданий масив впорядковується вибраним методом і способом. На екран виводиться відсортований масив та час сортування:

Рис. 3.8. Результат сортування

При виборі пункту меню “Порінвяти методи” заданий масив впорядковується усіма методами (спосіб сортування – за зростанням). Після цього перед користувачем з’являється вікно, в якому відображається порівняльна характеристика методів: час сортування, кількість операцій присвоєння і кількість операцій порівняння:

 

-29-

Рис. 3.9. Порівняння методів сортування

При виборі пункту меню “Вихід” програма закривається.

 

-30-

4. ПРОГРАМА  ТА МЕТОДИКА ВИПРОБУВАНЬ

У цьому розділі описано  випробування яким піддавалося програмне  забезпечення після його розробки.

 

4.1. Об’єкт  випробувань

 Об’єктом випробування  був скомпільований екземпляр  програмного забезпечення Sort розробленого у візуальному середовищі програмування Borland C++Builder 6.0.

 

4.2. Використані  технічні засоби

 Випробовування виконувалися на комп’ютері описаному вище  
(пункти 1.3.2 та 3.2)

 

4.3. Порядок  та методика випробувань

Програмне забезпечення було випробуване розробником для виявлення помилок у функціонуванні коду програми. До основних випробовувань необхідно віднести експертний аналіз (порівняння) вихідних результатів програмного продукту із реально присутніми. У випадку, коли величини співпадають, програма функціонує правильно, якщо ні, то необхідно перевірити код програми.

Основними причинами  відмов ПЗ, що призводять порушення  нормального функціонування можна  віднести наступні:

1. помилки, приховані в самій програмі;
2. спотворення вхідних даних, що підлягають обробці;
3. неправильність дії користувача;
4. несправність апаратних засобів, на котрих реалізується обчислювальний процес.

Після виявлення помилок  наступним кроком було коректування даних, усунено джерело їх спотворення. Взагалі, виправлення помилок є  одним з основних засобів підвищення надійності ПЗ.

 

-31-

При тестуванні даного програмного  забезпечення необхідно перевірити чи правильно сортується введений масив усіма методами і одним з двох способів (за зростанням чи за спаданням).

При правильній роботі програми на екрані повинен відображатися відсортований масив:

Рис 4.1. Сортування масиву

Ми бачимо, що масив  відсортовано, отже програма працює правильно. 

 

 4.4. Результати випробувань

 У результаті проведених випробувань програмне забезпечення працює правильно.

 Якщо користувач  під час випробувань програми  отримає відсортований масив, то можна стверджувати, що розроблене програмне забезпечення працює вірно.

При тестуванні програми на масиві 100000 елементів ми бачимо, що найкращим по усіх параметрах є  сортування Хоара:

 

-32-

Рис. 4.2. Порівняння характеристика методів  сортування

 

-33-

5. ВИСНОВКИ

 

Грунтуючись на результатах  проведених досліджень можна зробити висновки:

1. Розроблено програмне забезпечення Sort яке дозволяє відсортувати заданий масив одним із методів швидкого сортування;

2. Розроблене програмне  забезпечення надає такі можливості:

• задання початкових даних (випадковим чином, введених користувачем, прочитаних з файлу);
• реалізація швидких методів сортування масивів (сортування деревом, пірамідальне сортування, сортування Хоара, метод цифрового шифрування);
• порівняльна характеристика методів сортування;

3. Проведене тестування  програмного забезпечення дозволяє  зробити висновок про те, що  воно задовольняє умові технічного  завдання.

 

-34-

6. ВИКОРИСТАНА ЛІТЕРАТУРА

 

1. Айра П. Обьектно-Ориентированное прогрпммирование на С++. М.: Санкт-Петербург, 1999. - 460 с.
2. Архангельський А.Я. С++Builder 6: Справ. Пособие. Кн.1. Язык С++. - М.: Бином, 2004. - 544 с.
3. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. - М.:Издательский дом "Вильямс", 2000. - 750 с.
4. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997.
5. Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. - 240 с.

 

-35-

7. ДОДАТКИ

Додаток А. Код  програми

 

Project1;

 

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

 

#include <vcl.h>

#pragma hdrstop

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

USEFORM("Unit1.cpp", Form1);

USEFORM("Unit2.cpp", Form2);

USEFORM("Unit3.cpp", Form3);

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

WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)

{

        try

        {

                 Application->Initialize();

                 Application->CreateForm(__classid(TForm1), &Form1);

                 Application->CreateForm(__classid(TForm2), &Form2);

                 Application->CreateForm(__classid(TForm3), &Form3);

                 Application->Run();

        }

        catch (Exception &exception)

        {

                 Application->ShowException(&exception);

        }

        catch (...)

        {

                 try

                 {

                         throw Exception("");

                 }

                 catch (Exception &exception)

                 {

                         Application->ShowException(&exception);

                 }

        }

        return 0;

}

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

 

Unit1.h

 

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

 

#ifndef Unit1H

#define Unit1H

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

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

-36-

#include <Forms.hpp>

#include <Menus.hpp>

#include <Dialogs.hpp>

#include <Grids.hpp>

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

class TForm1 : public TForm

{

__published: // IDE-managed Components

        TMemo *Memo1;

        TMemo *Memo2;

        TMainMenu *MainMenu1;

        TMenuItem *N1;

        TMenuItem *N2;

        TMenuItem *N3;

        TMenuItem *N4;

        TOpenDialog *OpenDialog1;

        TSaveDialog *SaveDialog1;

        TMenuItem *N5;

        TMenuItem *N6;

        TMenuItem *N7;

        TMenuItem *N8;

        TMenuItem *N9;

        TMenuItem *N10;

        TMenuItem *N11;

        TMenuItem *N12;

        TMenuItem *N13;

        TMenuItem *N14;

        TMenuItem *N15;

        TMenuItem *N16;

        TMenuItem *N17;

        TLabel *Label1;

        TLabel *Label2;

        TEdit *Edit1;

        TLabel *Label3;

        void __fastcall N4Click(TObject *Sender);

        void __fastcall N2Click(TObject *Sender);

        void __fastcall N3Click(TObject *Sender);

        void __fastcall N5Click(TObject *Sender);

        void __fastcall N15Click(TObject *Sender);

        void __fastcall N17Click(TObject *Sender);

        void __fastcall N16Click(TObject *Sender);

private: // User declarations

public:  // User declarations

        __fastcall TForm1(TComponent* Owner);

};

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

extern PACKAGE TForm1 *Form1;

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

#endif

 

Unit1.cpp;

 

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

 

#include <vcl.h>

-37-

#pragma hdrstop

 

#include "Unit1.h"

#include "Unit2.h"

#include <fstream.h>

#include <iostream>

#include "Unit3.h"

 

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

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

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

}

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

int c,m;

void qs(int* mas,int first, int last, bool asc)

{

    int i = first, j = last, x = mas[(first + last) / 2];

 

    do {

        if (asc)

        {

        while (mas[i] < x) {i++; c++;}

        while (mas[j] > x) {j--; c++;}

        }

        else

        {

        while (mas[i] > x) {i++; c++;}

        while (mas[j] < x) {j--; c++;}

        }

        c++;

        if(i <= j) {

            c++;

            if (i < j)

               {

               m+=3;

               int tmp=mas[i];

               mas[i]=mas[j];

               mas[j]=tmp;

               }

            m+=2;

            i++;

            j--;

        }

    } while (i <= j);

    c++;

    if (i < last)

        qs(mas, i, last, asc);

    c++;

    if (first < j)

        qs(mas, first,j, asc);

-38-

}

 

 

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

{

        qs(mas, 1, len, asc);

}

 

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

 

void ConSwap(int* mas, int i, int j, bool asc)

{

if (asc)

{

c++;

if (mas[i] < mas[j])

    {

    m+=3;

    int tmp = mas[i];

    mas[i] = mas[j];

    mas[j] = tmp;

    }

}

else

{

c++;

if (mas[i] > mas[j])

    {

    m+=3;

    int tmp = mas[i];

    mas[i] = mas[j];

    mas[j] = tmp;

    }

}

}

 

void Conflict(int* mas, int i, int k, bool asc)

{

m++;

int j = 2*i;

c++;

if (j == k)

    ConSwap(mas, i, j, asc);

else if (j < k)

    {

    if (asc)

    {

    c++;

    if (mas[j+1] > mas[j])

        {

        j++;

        m++;

        }

    }

    else

-39-

{

    c++;

    if (mas[j+1] < mas[j])

        {

        j++;

        m++;

        }

    }

    ConSwap(mas, i, j,asc);

    Conflict(mas, j, k,asc);

    }

}

 

void SortTree(int* mas, int i, int len, bool asc)

{

c++;

if (i < len / 2)

    {

    SortTree(mas,2*i,len,asc);

    SortTree(mas,2*i+1,len,asc);

    Conflict(mas, i, len-1,asc);

    }

}

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

{

SortTree(mas, 1, len,asc);

for (int k=len;k>1;k--)

    {

    c++;

    m++;

    ConSwap(mas, k, 1,asc);

    Conflict(mas, 1, k - 1,asc);

    }

}

 

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

 

typedef struct tree

  {

    int data;

    struct tree *left;

    struct tree *right;

  } TREE;

 

TREE *add_to_tree(TREE *root, int new_value)

{

   if (root==NULL)

     {

        root = (TREE*)malloc(sizeof(TREE));

        root->data = new_value;

        root->left = root->right = 0;

        m+=3;

        return root;

     }

     c++;

-40-

if (root->data<new_value)

     {

     root->right = add_to_tree(root->right, new_value);

     m++;

     }

   else

     {

     root->left  = add_to_tree(root->left, new_value);

     m++;

     }

   return root;

}

 

void tree_to_array(TREE *root, int *mas,  bool asc)

  {

    static max2 = 1;

    if (mas[0]==-1)

       {

       max2=1;

       mas[0]=1;

      }

    c++;

    if (root==NULL) return;

    if (asc)

    {

    m++;

    tree_to_array(root->left, mas, asc);

    m++;

    mas[max2++] = root->data;

    m++;

    tree_to_array(root->right, mas,asc);

    free(root);

    }

    else

    {

    tree_to_array(root->right, mas, asc);

    mas[max2++] = root->data;

    m++;

    tree_to_array(root->left, mas, asc);

    free(root);

    }

  }

 

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

{

   TREE *root = NULL;

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

      {

      root = add_to_tree(root, mas[i]);

      m+=2;

      c++;

      }

   mas[0]=-1;

   tree_to_array(root, mas,asc);

}

-41-

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

 

void swap(int *index, int i, int j)

{

int tmp=index[i];

index[i]=index[j];

index[j]=tmp;

m+=3;

}

 

bool les(int *index, int mas[], int i, int j)

{

c++;

return mas[index[i]]<mas[index[j]];

}

 

bool gret(int *index, int mas[], int i, int j)

{

c++;

return mas[index[i]]>mas[index[j]];

}

 

void index_qs(int mas[], int *index, int l, int r, bool asc)

  {

    int i=l, j=r, x=(l+r)/2;

    if (asc)

    {

    do {

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

           {

           i++;

           m++;

           }

      while (les(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], index[j]);

          i++;