СПЕЦІАЛЬНЕ ЗАСТОСУВАННЯ ВЛАСНОЇ РОЗРОБКИ ДЛЯ ДЕМОНСТРАЦІЇ І ПОРІВНЯННЯ АЛГОРИТМІВ СОРТУВАННЯ ТА ПОШУКУ ДАНИХ
15.05.2020
СПЕЦІАЛЬНЕ ЗАСТОСУВАННЯ ВЛАСНОЇ РОЗРОБКИ ДЛЯ ДЕМОНСТРАЦІЇ І ПОРІВНЯННЯ АЛГОРИТМІВ СОРТУВАННЯ ТА ПОШУКУ ДАНИХ
Анотація. У статті наведено опис спеціального застосування власної розробки, що дозволить студентам, які вивчають алгоритми сортування та пошуку даних, спостерігати за процесом і проводити аналіз переваг і недоліків низки методів для кращого розуміння принципів їх роботи. Розглянуто деякі алгоритми сортування та пошуку даних, проаналізовано існуючі програмні системи (інтернет-сайти) для рішення поставленої задачі, їхні недоліки. Виконано розробку об’єктно-орієнтованої моделі програмної системи засобами візуального моделювання UML та функціональної моделі в нотаціях BPWin. Наведено приклад роботи розробленого застосування.Вивчення алгоритмів сортування та пошуку даних передбачено багатьма освітніми програмами спеціальностей галузі знань «Інформаційні технології». Було поставлено завдання створення програми (застосування) для демонстрації та порівняння алгоритмів сортування та пошуку даних з метою кращого розуміння принципів їх роботи цільовою аудиторією (студентами 1-го курсу). Створювана прикладна програма має бути націлена на простоту і автономність.
Для демонстрації роботи має відображатися тільки кількість ітерацій (кроків алгоритму), тому що реальний час роботи алгоритму занадто малий, і користувач не встигне зрозуміти принципів його роботи. Для вирішення даної проблеми треба додати затримку після кожного кроку алгоритму, що суттєво збільшить час роботи, який складає:
T = tі + tз * N, (1)
де T – загальний час роботи алгоритму;
tі – час однієї ітерації;
tз – час затримки;
N – кількість ітерацій.
Під час порівняння алгоритмів такої проблеми не виникне, тому що розмір масиву багаторазово зросте, і час роботи отже так само. Тому затримку можна буде прибрати, і показаний час роботи буде відповідати реальному.Розглянемо типову послідовність роботи із розробленим застосуванням. Після запуску програми відкривається головна форма, на якій розташовано головне меню програми, відповідне за всі основні функції програми, елементи масиву і поля для початкових значень.
Для демонстрації роботи алгоритму необхідно заповнити масив і вибрати алгоритми сортування та/або пошуку. Масив можна заповнити автоматично – другий пункт меню, доступні три варіанти: найкращий і найгірший випадок, випадкове заповнення. Можна вручну заповнити масив довільними цілими числами, для цього виділіть один з елементів масиву мишкою і введіть потрібне значення.
Після заповнення вибирається потрібний алгоритм сортування та / або пошуку з відповідного списку. Доступні алгоритми: бульбашкове сортування; сортування вставками; сортування вибором; сортування злиттям; швидке сортування; шейкерне сортування; сортування гнома; сортування Шелла; бінарне сортування; послідовний пошук; бінарний пошук.
Якщо був обраний алгоритм пошуку, слід вказати шуканий елемент в полі праворуч від списку алгоритмів сортування. Для запуску демонстрації слід вибрати перший пункт головного меню програми.
Якщо обрано бінарний пошук і в якості вихідних даних подано не відсортований масив, програма самостійно відсортує його «швидким» сортуванням. Час, витрачений на це, не буде враховуватись під час підрахунку роботи алгоритму бінарного пошуку. Це необхідно, тому що бінарний пошук може працювати тільки з відсортованими масивами.
Після закінчення роботи прикладна програма видає час роботи алгоритмів, кількість ітерацій і індекс шуканого елемента, якщо був задіяний алгоритм пошуку. У разі коли масив не містить шуканого елемента, в якості індексу шуканого елемента буде виданий нуль.
Для порівняння алгоритмів сортування слід вибрати третій пункт меню. Відкриється нова форма в якій слід вибрати зі списку один з можливих варіантів заповнення і ввести розмір масиву в відповідні поле. Потім проводиться запуск процесу роботи – натискання кнопки «Змоделювати».
Час роботи алгоритмів залежить від обчислювальної потужності ЕОМ, і робота з великими масивами може зайняти досить багато часу. В процесі оброблення даних результати роботи будуть виводиться в дві стовпчасті діаграми: час роботи – верхня, і кількість ітерацій – нижня.
Для перегляду сутності кожного з алгоритмів сортування та пошуку даних, які використовуються в даній програмі, слід звернутися до довідки – четвертий пункт головного меню програми. Відкриється нове вікно програми, де можна вибрати потрібний алгоритм зі списку, як на головній формі програми. Опис буде показано у вікні в нижній частині форми.
Коротка довідка про програму розташована на цій же формі. Для її перегляду слід натиснути кнопку «Про програму».
Крім усього іншого користувачеві доступна зміна мови інтерфейсу програми (доступні російська, українська і англійська мови)
Назва конкурсу: Конкурс «Кращий інноваційний диплом (проект)»
ПІБ конкурсанта: Сокольський Олександр Сергійович
Країна: Україна
Область: Донецька область
Назва НЗ: Донбаська державна машинобудівна академія
Учасник фіналу: Так
Місце Фінал: 3
Файл статті (pdf): Завантажити
