Побудова блок-схеми алгоритму сортування

На основі опису алгоритму проста вставка побудуємо блок - схему

2.2 Опис блок схеми алгоритму сортування

Крок 1 : Підрахунок (Початок циклу підрахунку).

Крок 2 : Одержання відсортованого масиву.

Ітераційно (i…n) починаючи з i=1, перебираємо елемента для кожного вибраного числа n, збільшуємо значення в комірці масиві проста вставка з індексом m, на одиницю. Далі припустимо що i=i+1. Якщо i<n – переходимо на m_j<r_j , тоді місце елемента, що m_i вставляє – j осередок, інакше – вихід з циклу.

Наприклад, якщо зустрілися масиви m=0, збільшуємо значення нульової комірки на 1. якщо зустріли четвірку, збільшуємо значення комірки на 1.

В результаті підрахунків в кожній i – й комірці простої вставки буде записане число. Яке показує в скільки разів число i(з діапазону [1, n]) зустрілися в масиві m.

Далі припустимо , що j=0 ітераційно (i = l,…, n ), починаючи з i=1 перебираємо комірки масива проста вставка : якщо m_i > 0 тоді : вважаємо , що r_j=i, j=i+1 перехід на r_p+1 =r_p.

Таким чином, якщо значення mi в i-ої комірки проста вставка була більше нуля (сі >0) тоді сі =2, то в початковому масиві m зустрілися дві одиниці і в результуючий масив буде виведено дві одиниці. Припустимо: i=i+1, якщо і≥к. Перехід до наступної інтеграції: записуємо rp+1=rp, інакше сортування закінчено, вихід з циклу. Інакше ітераційно (j=j,…,n) дописуємо елементи в кінці масива. Припустимо, що i=j=1, k=k+1, якщо j≤n, перехід: записуємо rp+1=rp, думаємо p=p-1: якщо p≥j

2 Програмна реалізації алгоритму сортування

2.1 Програмна реалізація алгоритму сортування

Згідно до блок схеми алгоритму наведеної раніше розроблена програмна реалізація алгоритму проста вставка яка наведена нижче.

2.2 Опис програмної реалізації алгоритму сортування

Згідно побудованої блок-схеми алгоритму проведеної в підрозділі 1.2 розроблена програмна реалізація алгоритму проста вставка яка поділяється на частини приведені нижче.

1. Описуюча частина, в якій підключається бібліотеки, описуються константи та змінні.

2. Введення данних, в якій масив заповнюється данними( за допомогою генератора випадкових чисел).

3. Сортування, в якій масив сортуються.

4. Виведення результатів, в якій виводяться відсортований масиви.

2.3 Опис отриманих результатів

В якості вихідних даних в нас було задано вихідний масив з 80 пріоритетних цілей, з виконанням оператора випадкових чисел. Після виконання програмної реалізації алгоритму проста вставка наведена в підрозділі 2.1 отримуємо наступні результати:

Отримані результати були перевірені за 3 критеріями:

1) Кількісний критерій – кількість чисел в початковому і кінцевому масиві збігаються.

2) Критерій складу – кількість цифр одного достоїнства в початковому та кінцевому масиві.

3) Критерій відношення – кожна наступна цифра відсортованого масиву більша або дорівнює попередній.

3. Оцінка трудомісткості сортування

3.1 Аналітична оцінка трудомісткості сортування

Кожен алгоритм сортування характеризується трудомісткістю, яка являє собою Т(n) числа елементів n=n+1 масиву що сортується. При оцінці трудомісткості алгоритм сортування в першому наближені прийнято до уваги тільки кількість операцій порівнянь, що потребують для повного сортування масиву. Трудомісткість алгоритмів залежить не тільки від числа елементів масиву, що підлягають сортуванню, ай ще від інших характеристик. Для всіх алгоритмів обов’язкова степінь упорядкованості масиву – чим вона більше, тим трудомісткість менша.

Трудомісткість алгоритм проста вставка оцінюється так;

2

T1(n)=0.75∙n

Трудомісткість алгоритм лічильник залежить від параметра n,k.

T2(n,k)=2(n+k)

Трудомісткість алгоритм бульбашка залежить від параметра n.

2

T3(n)=n

Трудомісткість алгоритм злиття залежить від параметра n.

T4(n)=5n

3.2 Графічне представлення оцінки трудомісткості сортування

Згідно з критеріями оцінки трудомісткості наведених в п. 3.1 можна виконати наступний аналіз трудомісткості.

3.3 Аналіз отриманих результатів

З отриманих результатів можна побачити, що трудомісткість даної програми залежить від функції

2

T1(n)=0.75∙n

Підставивши кількісне значення цілей у формулі отримали:

Я отримав велике значення, тому трудомісткість моєї програми висока, а отже для кращого сортування необхідно використовувати алгоритм ‹Лічильник› чи ‹Бульбашка› тому що вони мають меншу, а тому і найкращу трудомісткість.

Висновки

В процесі виконання курсової роботи я отримав навички,як за допомогою

ЕОМ підготувати та вирішувати розрахункові задачі військового та прикладного характеру.

В результаті обчислення військово – прикладної задачі я:

У першому розділі будував блок схему

У другому розділі будував програмну реалізацію курсової роботи, отримав результати, оцінив роботу алгоритмів.

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

В процесі виконання роботи я отримав навички самостійного вирішення задач. Навчився вирішувати військово-прикладні задачі за допомогою програм: MS Office, Pascal, Mathcad.

Список використаних джерел

1. Обчислювальна техніка і програмування. Навчальна література. Під ред. Е.И. Бобира, ХВУ 1994г.

2. В.Е. Клімнюк, А.А. Попеленко. Обчислювальна техніка і програмування. Збірка задач. ХВУ,1994г

3. Д.П. Лабенко, В.А. Толстохатько. Обчислювальна техніка і програмування. Методичні рекомендації по виконанні курсової роботи. ХВУ,1996г.

4. Навчальний посібник. Толстохатько В.А та ін. Застосування персональних ЕОМ для розв’язання військово-прикладних задач. Частина1. Використання персональних ЕОМ для розв’язання оперативно- тактичних задач.Харків: ХВУ,2002.

5.Конспект лекцій.,Молодожонов С.М., Федотенков А.Н. Применение персональних микро-ЭВМ для решения военно-прикладных задач.- Харків: ВІРТА,1991.

6. Навчальний посібник .Бобир Е.И и др. Обчислювальна техніка і програмування. Харків:ХВУ,1994.

7. Підручник для ВНЗ. Симонович С.В. и др.. Інформатика. Базовий курс.-СПб.: Пітер,2001.