Information technologies and computer sciences

Classification Analysis of Sorting Methods

Authors

T. B. Martyniuk
Vinnytsia National Technical University ROR
B. I. Krukivskyi
Vinnytsia National Technical University ROR
DOI https://doi.org/10.31649/1997-9266-2023-168-3-77-83

Keywords

sorting ranking numerical array time dependence

Abstract

The basic procedure in many search systems is associative processing, namely the processes of sorting, ranking, and selection by key. These processes are important due to the need to speed up the work of the corresponding algorithms, where certain elements of the data array need to be frequently accessed. The need for parallel methods and tools for associative processing of large data sets is also related to the area of their effective application, for example, in relational databases, knowledge bases, expert systems, and the analysis of semantic networks. In this article, the analysis of the functional and implementation possibilities of the sorting process by known and alternative methods, taking into account time dependencies, was carried out. The applied aspect of the application of sorting and ranking operations in such areas as median filtering during pre-processing of signals and images, neural network classification of objects, and decision support subsystem in expert systems is considered. A classification model of one-dimensional array sorting methods is proposed, which are divided into two groups according to such a feature as the use of the pairwise comparison operation and the permutation of the elements of the numerical array. The first group consists of classic sorting methods, and the second group contains alternative sorting methods with slice processing. In the table, the characteristics of the sorting methods of the first group are considered according to such characteristics as the total number of comparisons and the average number of moves, which correlate with the time and hardware costs of their implementation, respectively. The functional structure of vertically-parallel processing of a one-dimensional array of numbers using decrement and increment operations is given as an example of the sorting method of the second group. At the same time, it is shown that the use of high-speed operations of increment and decrement as a result makes it possible to determine the maximum, minimum, and average element of the array by size. A comparison of the given time dependences of the two groups of algorithms shows that the sorting methods of the second group have a higher speed or a speed that does not depend on the number of elements of the array being sorted. At the same time, the hardware implementation of the sorting methods of both groups is in most cases implemented on devices with a sufficient level of regularity of the structure, but with different degrees of hardware costs.

475 276

How to Cite

[1]
“Classification Analysis of Sorting Methods ”, Вісник ВПІ, no. 3, pp. 77–83, Jun. 2023, doi: 10.31649/1997-9266-2023-168-3-77-83.

Author Biographies

T. B. Martyniuk, Vinnytsia National Technical University

Dr. Sc. (Eng.), Professor, Professor of the Chair of Computer Engineering

B. I. Krukivskyi, Vinnytsia National Technical University

Post-Graduate Student of the Chair of Computer Engineering

References

Р. Седжвик, Фундаментальные алгоритмы на С++. Анализ. Структура данных. Сортировка. Поиск. СПб.: ООО «ДиаСофтЮП», 2002, 688 с.
Е. А. Яценко, «Регулярные схемы алгоритмов адресной сортировки и поиска,» Управляющие системы и машины, № 5, с. 61-66, 2004.
D. E. Knuth, The Art of Computer Programming. V.3, Sorting and Searching. Reading: Addison-Wesley Longman, Inc., 1998, 800 p.
І. Г. Цмоць, Інформаційні технології та спеціалізовані засоби обробки сигналів і зображень у реальному часі, моногр. Львів, Україна: Видавництво УАД, 2005, 228 с.
І. Г. Цмоць, і В. Я. Антонів, «Апаратні засоби сортування даних методом злиття в реальному часі,» Інформаційні системи та мережі, № 814, с. 171-185, 2015. https://ena.lpnu.ua/handle/ntb/29774 .
І. Г. Цмоць, і В. Я. Антонів, «Алгоритми та паралельні структури сортування даних методом вставки,» Науковий вісник НЛТУ України, вип. 26.1, с. 340-350, 2016. https://doi.org/10.15421/40260153 .
Г. Е. Цейтлин, «Распараллеливание алгоритмов сортировки,» Кибернетика, т. 24, № 6, с. 67-74, 1989.
В. П. Кожемяко, Т. Б. Мартынюк, и В. В. Хомюк, «Особенности структурного программирования синхронных алгоритмов сортировки,» Кибернетика и системный анализ, № 5, с. 122-133, 2006.
Т. Б. Мартинюк, і Б. І. Круківський, «Модель паралельного сортувальника масиву чисел,» Вісник Вінницького політехнічного інституту, № 5 (152), с. 49-55, 2020. https://doi.org/10.31649/1997-9266-2020-152-5-49-55
Т. Б. Мартинюк, і Б. І. Круківський, «Особливості паралельного алгоритму сортування з формуванням рангів,» Кібернетика та системний аналіз, т. 58, № 1, с. 31-36, 2022.
Т. Б. Мартинюк, О. І. Черняк, Б. І. Круківський, і Мохамед Салем Нассер Мохамед, «Обчислювальна складність мережевої моделі сортування лінійного масиву чисел,» Інформаційні технології та комп’ютерна інженерія, № 2, с. 64-71, 2019. http://ir.lib.vntu.edu.ua//handle/123456789/30531 .
Т. Б. Мартинюк, Мохамед Салем Нассер, і В. В. Власійчук, «Модель сортувальної мережі,» Інформаційні технології та комп’ютерна інженерія, № 3, с. 217-220, 2005.
Г. М. Гнатієнко, і В. Є. Снитюк, Експертні технології прийняття рішень, моногр. Київ, Україна: ТОВ «Маклаут», 2008, 444 с.
А. Ш. Непомнящая, и М. А. Владыко, «Сравнение моделей ассоциативного вычислителя,» Программирование, № 6, с. 41-50, 1995.
T. Kohonen, Content-Addressable Memories. Springer-Verlag Berlin Heidelberg, 1987, 388 р.
H. Lorin, Sorting and Sort Systems. Mass.: Addison-Wesley Publishing Company, 1975, 373 р.
W. K. Pratt, Introduction to Digital image Processing. Reading: Taylor and Francis Group, Inc, 2014. 371 р.
T. B. Martyniuk, et all, «Neural network approach to numeric array sorting,» Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments: Proceedings of SPIE 11176, 111761N (6 November), 2019. https://doi.org/10.1117/12.2535916 .
А. В. Палагин, и В. Н. Опанасенко, Реконфигурируемые вычислительные системы. Киев, Украина: Просвіта, 2006, 295 с.
В. И. Осинский, Т. Б. Мартынюк, А. А. Козлов, и Мохамед Салем Нассер Мохамед, «Особенности оптоэлектронной реализации сортирующей нейросети,» Оптико-електронні інформаційно-енергетичні технології, т. 18, № 2, с. 58-67, 2009.
V. P. Kozhemyako, T. B. Martyniuk, R. A. Rasenko, and L. L. Pekhan, «Structure of optoelectronic sorting memory,» Оптико-електронні інформаційно-енергетичні технології, № 1 (3), с. 26-30, 2002.
В. Р. Григорьев, и С. П. Наумов, «Нейросетевая организация алгоритма сортировки на трехмерном оптическом нейрочипе,» Автометрия, № 3, с. 28-37, 1993.
Т. Б. Мартинюк, Н. О. Денисюк, і Б. І. Круківський, «Асоціативні процесори з паралельно-послідовною обробкою даних,» Інформаційні технології та комп’ютерна інженерія, № 1 (44), с. 27-36, 2019. https://doi.org/10.31649/1999-9941-2019-44-1-27-36 .
Т. Б. Мартинюк, Л. В. Крупельницький, і Б. І. Круківський, «Регулярна обчислювальна структура для ранжування даних,» Інформаційні технології та комп’ютерна інженерія, № 3 (52), с. 70-76, 2021. https://doi.org/10.31649/1999-9941-2021-52-3-70-76
Т. Б. Мартинюк, Б. І. Круківський, і О. А. М’якішев, «Особливості моделей нейромережного класифікатора для розпізнавання об’єктів,» Вісник Вінницького політехнічного інституту, № 4 (163), с. 56-63, 2022. https://doi.org/10.31649/1997-9266-2022-163-4-56-63 .
T. B. Martyniuk, B. I. Krukivsyi, L. M. Kupershtein, and V. V. Lukichov, «Neural network model of heteroassociative memory for the classification task,» Radioelectronic and Computer Systems, № 2 (102), pp. 108-114, 2022. https://doi.org/10.32620/reks.2022.2.09 .
] А. Ш. Непомнящая, «Сравнение алгоритмов Прима-Дейкстры и Краскала с помощью ассоциативного параллельного процессора,» Кибернетика и системный анализ, т. 36, № 2, с. 19-27, 2000.
] Т. Б. Мартынюк, и В. В. Хомюк, «Особенности математической модели дискретного SM-преобразования,» Математичні машини і системи, № 4, с. 145-155, 2010. http://dspace.nbuv.gov.ua/handle/123456789/83330 .
] Т. Б. Мартинюк, А. В. Кожем’яко, Б. І. Круківський, і А. Г. Буда, «Асоціативні операції на базі різницево-зрізової обробки даних», Вісник Хмельницького національного університету, № 4 (311), с. 159-163, 2022. https://doi.org/10.31891/2307-5732-2022-311-4-159-163 .
Т. Б. Мартинюк, Д. О. Каташинський, М. В. Микитюк, і М. О. Зайцев, «Особливості обчислювальних процесів на базі SM-перетворення,» Оптико-електронні та інформаційно-енергетичні технології, № 2 (44), с. 32-37, 2022. https://doi.org/10.31649/1681-7893-2022-44-2-32-37 .
В. Ф. Гузик, В. Е. Золотовский, и С. А. Чиненков, «Организация различных методов сортировки в вычислительных системах,» Электронное моделирование, № 3 (14), с. 25-28, 1992.
А. С. Мельничук, С. П. Луценко, Д. С. Громовий, і М. В. Трофимова, «Аналіз методів сортування масиву чисел,» Технологический аудит и резервы производства, № 4/1 (12), с. 37-40, 2013.
Т. Б. Мартинюк, А. В. Кожем’яко, А. І. Колівошко, і О. В. Карась, «Дослідження ефективності кільцевої сортувальної мережі,» Інформаційні технології та комп’ютерна інженерія, № 1, с. 68-71, 2015.
Т. Б. Мартынюк, Л. И. Тимченко, А. В. Кожемяко, и Л. М. Куперштейн, «Эффективность посрезовой обработки векторных массивов данных,» Математичні машини і системи, № 2, с. 60-67, 2017.
http://dspace.nbuv.gov.ua/handle/123456789/125561 .
Т. Б. Мартынюк, «Организация ассоциативного процессора с поразрядно-последовательной обработкой информации», Электронное моделирование, т. 18, № 3, с. 28-31, 1996.
T. Martyniuk, T. Vasilyeva, V. Suprigan, and M. AL-Heyari, «Features of sorting memory realization», Proceedings of SPIE-The International Society for Optical Engineering, vol. 4425, pp. 89-91, 2001.
Т. Б. Мартынюк, А. В. Кожемяко, и В. В. Хомюк, «Модели систолических массивов для обработки векторных данных по разностным срезам», Управляющие системы и машины, № 5, с. 46-55, 2009.

Most read articles by the same author(s)

1 2 > >>