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

-6-

ЗМІСТ

 ЗАВДАННЯ НА КУРСОВУ  РОБОТУ…………………………………………...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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ТЕОРЕТИЧНА  ЧАСТИНА

 

-9-

1. ТЕХНІЧНЕ  ЗАВДАННЯ

 

1. Підстави для розробки

Розробка програмного  забезпечення виконується на підставі рішення засідання кафедри ПЗКС про затвердження тем дипломних та курсових робіт (протокол № __ від ____________ 20___ року).

1.2. Призначення розробки

У розробленому програмному забезпеченні (ПЗ) запрограмовані швидкі методи сортування масивів такі як сортування деревом, пірамідальне сортування, сортування Хоара та метод цифрового шифрування.

1.3. Аналіз вимог  до програмного забезпечення

 

1.3.1. Функціональні вимоги

До функціональних вимог розробленого програмного забезпечення відноситься:

1. задання початкових даних (випадковим чином, введених користувачем, прочитаних з файлу);
2. реалізація швидких методів сортування масивів;
3. візуальне подання результатів сортування;
4. подання результатів сортування у вигляді файлу на жорсткому диску;
5. візуальна оцінка швидкодії сортування;
6. порівняльна характеристика методів сортування;
7. забезпечення зручного графічного інтерфейсу користувача.

 

1.3.2. Вимоги до складу та параметрів  технічних засобів

Розроблений програмне забезпечення працює у таких операційних системах (ОС) як: Windows /98/ME/NT/XP. Системними вимогами, за якими ПЗ працюватиме та буде видавати достовірні результати, можна вважати:

• процесори 6-го покоління (типу АМD, Pentium 300 МГц і вище);

• об’єм оперативної  пам’яті 256 Мб. і вище;

-10-

• графічні адаптери з пам’яттю 64 Мб. і вище;

• жорсткий диск ємністю 2 Гб. і вище;

• приводи та USB-порти.

 

1.3.3 Вимоги до інтерфейсу

Інтерфейс програми повинен  забезпечувати просту візуалізацію даних.

Інтерфейс повинен бути багатовіконним. Засоби керування та введення, візуалізації необхідно розмістити на одній формі, яка легко масштабується.

 

1.3.4. Вимоги до інформаційної та  програмної сумісності

Розроблене програмне  забезпечення повинно працювати  в ОС Windows, тому для коректної роботи ПЗ необхідне стабільне функціонування ОС. У випадку, коли виявлені приховані помилки у програмі, необхідно встановити пакет інструментальних засобів Borland С++ Builder 6.0. Додаткових вимог до інформаційної і програмної сумісності не висувається.

 

1.3.5. Вимоги до тестування програмного забезпечення

Для перевірки правильності функціонування розробленого програмного  забезпечення необхідно провести наступні тестування:

1. Тестування інтерфейсу;
2. Тестування режимів роботи.

 

1.4. Вимоги до  програмної документації

 

1.4.1. Склад до супроводжувальної документації

Програмне забезпечення постачається з наступною програмною документацією:

1. Технічне завдання;
2. Опис мови програмування;
3. Опис програми;
4. Програма та методи тестування.

-11-

Програмна документація постачається в електронному вигляді на CD-ROM

1.4.2. Вимоги до супроводжувальної документації

Вимоги до оформлення:

• файли Microsoft Word;
• шрифт 14 пунктів;
• вирівнювання по ширині аркуша;
• міжрядковий інтервал 1,5 пункти.

 

1.5. Стадії та етапи розробки

№ п/п	Назва етапів  кваліфікаційної  роботи	Термін виконання етапів роботи	Примітка
1	Отримання завдання на курсову роботу	01.02.2011
2	Обробка літератури даних	14.02. 2011
3	Вибір математичної моделі	21.02. 2011
4	Розробка програмного забезпечення	24.03. 2011
5	Тестування програмного забезпечення	01.04. 2011
6	Написання курсової роботи	10.04. 2011
7	Захист курсової роботи	згідно розкладу

 

1.6. Порядок  контролю і приймання

Програма повинна бути випробувана та протестована виробником на наявність помилок.

Порядок контролю і приймання  проекту полягає у наступному:

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

 

-12-

Програма та програмна  документація повинна бути виконана на 100 % і пройти рецензування згідно графіку.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРАКТИЧНА ЧАСТИНА 
-14-

2. АРХІТЕКТУРА, ФУНКЦІОНАЛЬНІ ТА ТЕХНІЧНІ

ПОКАЗНИКИ

В цьому розділі описано програмні, апаратні та архітектурні рішення необхідні для розробки та супроводу цього програмного продукту.

Програма розроблена в інтегрованому середовищі програмування Borland C++Builder 6.0 та працює під управлінням операційних систем Windows 9x/NT/XP. Вивід даних здійснюється на формі програми, що можна спостерігати на моніторі.

 

2.1. Призначення та область застосування

Розроблене програмне забезпечення призначено для сортування масивів швидкими методами сотування такими як сортування деревом, пірамідальне сортування, сортування Хоара та метод цифрового шифрування. Також дане ПЗ дозволяє провести порівнялну характеристику вищенаведених методів.

 

2.2. Опис та  обгрунтування обраної архітектури

Функціональність програмного  забезпечення полягає у роботі оного модуля. Робота цього модуля полягає у:

1) заданні початкових даних (випадковим чином, введених користувачем, прочитаних з файлу);

2) сортуванні заданого масиву одним із швидких методів сортування;

3) виведенні результатів сортування на екран;

4) проведенні порівняльної характеристики швидких методів сортування на заданій послідовності чисел.

Блок схему програми наведено на рис 2.1.

 

 

 

 

 

 

-15-

 

Рис 2.1. Блок-схема

2.3. Опис алгоритму і функціонування програми

2.3.1 Сортування деревом

Алгоритм сортування деревом власне кажучи є поліпшенням  алгоритму сортування вибором. Процедура  вибору найменшого елемента удосконалена як процедура побудови так званого сортуючого дерева. Сортуюче дерево - це

-16-

структура даних, у якій представлений процес пошуку найменшого елемента методом попарного порівняння елементів, що стоять поруч.  Алгоритм сортує масив у два етапи.

• I етап : побудова сортуючого дерева;
• II етап : просування елементів по сортуючому дереву.