Стаття. Мартинюк Т. Б.. Обчислювальна складність мережевої моделі сортування лінійного масиву чисел Вычислительная сложность сетевой модели сортировки линейного массива чисел Computational complexity of the network model of sorting of a linear number array

Реєстраційний номер

2119U010900, Матеріали видань та локальних репозитаріїв

Категорія

Стаття

Назва роботи

Обчислювальна складність мережевої моделі сортування лінійного масиву чисел Вычислительная сложность сетевой модели сортировки линейного массива чисел Computational complexity of the network model of sorting of a linear number array

Автор

Мартинюк Т. Б.
Черняк О. І.
Круківський Б. І.
Мохамед Салем Нассер Мохамед
Martyniuk T. B.
Chernyak O. I.
Krukivskyi B. I.
Mohamed Salem Nasser Mohamed
Мартынюк Т. Б.
Черняк А. И.
Круковский Б. И.
Martyniuk T. B.
Chernyak O. I.
Krukivskyi B. I.
Mohamed Salem Nasser Mohamed

Дата публікації

01-01-2019

Постачальник інформації

Вінницький національний технічний університет

Першоджерело

http://ir.lib.vntu.edu.ua/handle/123456789/30531

Видання

Вінницький національний технічний університет

Опис

При розробці розвиненого програмного та апаратного забезпечення для сучасних обчислювальних засобів інтерес представляють удосконалені методи асоціативної обробки інформації, а саме процедури сортування і вибору. Це забезпечує реалізацію ефективного пошуку потрібної інформації в масивах даних. Необхідність паралельної необчислювальної обробки великих масивів інформації потребує відповідну організацію асоціативної пам'яті, а також розробку і використання відповідних перспективних технічних засобів. Сортування вважається важливою процедурою в таких прикладних областях, як рішення економічних задач, управління базами даних (СУБД), сортування IP адрес в комп'ютерних мережах, обробка сигналів і зображень (наприклад, при нелінійній медіанній фільтрації зображень). Аналіз відомих методів сортування показав, що найбільш ефективним методом паралельного сортування з урахуванням його апаратної реалізації сортуючою мережею є метод попарного обміну. При цьому, ступінь паралелізму будь-якого методу сортування за його апаратної реалізації безпосередньо залежить від кількості схем порівняння, які спрацьовують паралельно при кожному перегляді. Для методу попарного обміну ступінь паралелізму визначається величиною ]n/2[, де n - кількість вхідних числових величин або розмірність вхідного лінійного масиву чисел. У статті проаналізовано способи реалізації алгоритму сортування методом попарного обміну з топологією зв'язків між елементами масиву чисел у вигляді «стрічки» і «кільця». Для прикладу описано паралельний алгоритм сортування методом попарного обміну. Моделювання алгоритму виконано на мові високого рівня С ++. Проаналізовано отримані статистичні та графічні результати моделювання. Аналіз графічних результатів моделювання свідчить про залежність виду O(n) між кількістю циклів сортування і розмірністю n вхідного масиву. Це підтверджує ефективність апаратної реалізації сортування попарним обміном на сортуючій мережі за рахунок регулярності структури і зв'язків в процесі сортування. Можливість статистично визначити не тільки кількість циклів сортування при заданій розмірності масиву чисел, але й відповідну кількість порівнянь і переміщень значно розширює можливості вдосконалення відомих і створення нових способів синхронного сортування елементів лінійного масиву апаратно у вигляді сортуючої мережі.

Додано/оновлено в НРАТ

2026-11-04