Analysis of methods for number array sorting

Authors

  • Андрій Сергійович Мельничук Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021, Ukraine
  • Сергій Петрович Луценко Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021, Ukraine
  • Дмитро Сергійович Громовий Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021, Ukraine
  • Карина Вікторівна Трофимова Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021, Ukraine

DOI:

https://doi.org/10.15587/2312-8372.2013.16239

Keywords:

sorting, array of numbers, operating speed, integration, memory capacity, algorithm, programming

Abstract

This article considers the methods of sorting, i.e. placing the array of numbers, which are used in computer techniques today, according to the rule. Sorting is one of the most common principles of programming systems, while their application for various applied problems requires choosing an optimal sorting algorithm from a set of existing ones. The objective of the article is to analyze temporal characteristics of the selection process aimed at choosing the algorithm, which is the most suitable for a certain goal realization.

Existing methods of sorting can be grouped into: sorting by insertion, sorting by selection, sorting by exchange.

Existing methods are analyzed in terms of quantity indexes of exchanges, integrations and comparisons that define each algorithm at most. As a result, the total operating speed of each method was estimated; the advantages and disadvantages of each method were singled out.

The results of analysis of well known sorting methods allow choosing the best method for software and hardware implementation from this point of view. The principal possibility of new solutions in the field of hardware implementation was shown in order to increase the level of parallelism and accelerate the sorting process, whereby the sorting method by exchange should be prerogative.

After checking the known sorting methods for operating speed with the use of the constant volume array, the operation time of sorting programs was defined on the basis of different sorting methods. Yet, the sorting method of Shell and quick sort method have shown best results.

Author Biographies

Андрій Сергійович Мельничук, Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021

Department of radiotechnics

Сергій Петрович Луценко, Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021

Department of radiotechnics

Дмитро Сергійович Громовий, Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021

Department of radiotechnics

Карина Вікторівна Трофимова, Vinnytsia National Technical University, 95 Khmelnytske shose, Vinnytsia, 21021

Department of medical and biological apparatuses design

References

  1. Лэнгсам, Й. Структуры данных для персональных ЭВМ [Текст] / Й. Лэнгсам, М. Огенстайн, А. Тененбаум. – М. : Мир, 1989. – 568 с.
  2. Вышинский, В. А. Сортировка чисел в матрично-алгебраической ЭВМ [Текст] / В. А. Вышинский // Управляющие системы и машины. – 2001. – № 2. – С. 50–52.
  3. Лорин, Г. Сортировка и системы сортировки [Текст] / Г. Лорин. – М. : Мир, 1983. – 384 с.
  4. Вирт, Н. Алгоритмы + структуры данных = программа [Текст] / Н. Вирт. – М. : Мир, 1985. – 406 с.
  5. Программирование алгоритмов обработки данных [Текст] / О. В. Ускова, Н. В. Огаркова, И. Е. Воронина и др. – СПб. : БХВ-Петербург, 2003. – 102 с.
  6. Гузик, В. Ф. Организация различных методов сортировки в вычислительных системах [Текст] / В. Ф. Гузик, В. Е. Золотовский, С. А. Чиненков // Электронное моделирование. – 1992. – Т. 14, № З. – С. 25–28.
  7. Hea, M. An optimal and processor efficient parallel sorting algorithm on a linear array with a reconfigurable pipelined bus system [Text] / M. Hea, X. Wua, S. Q. Zhengb // Computers & Electrical Engineering. – 2009. – Vol. 35, Issue 6. – pp. 951–965.
  8. Кнут, Д. Э. Искусство программирования. Т. 3. Сортировка и поиск [Текст] / Д. Э. Кнут. – 2-е изд. – М. : Вильямс, 2003. – 832 с.
  9. Chandra, S. Sorting algorithms on transputer arrays [Text] / S. Chandra, M. Jain, A. Basu, P. S. Kumar // Parallel Computing. – 1993. – Vol. 19, Issue 6. – pp. 595–607.
  10. Lin, Y.-C. Parallel sorting with cooperating heaps in a linear array of processors [Text] / Yen-Chun Lin, Ferng-Ching Lin // Parallel Computing. – 1990. – Vol. 16, Issue 2–3. – pp. 273–278.
  11. Lengsam, Y., Ogenstain, M., Tenenbaum, A. (1989). Struktury dannykh dlya personalnykh EVM [Data structures for personal ECM]. Moscow, 568 p.
  12. Vyshynskiy, V. A. (2001) Sortirovka chisel v matrichno-algebraicheskoy EVM [Numbers sorting in matrix-algebraic ECM]. Upravlyayushchiye sistemy i mashiny – Control systems and machines, 2, 50–52.
  13. Lorin, G. (1983). Sortirovka i sistemy sortirovki [Sorting and sorting systems]. Moscow, 384 p.
  14. Wirt, N. (1985). Algoritmy + struktury dannykh = programma [Algorithms + data structures = program]. Moscow, 406 p.
  15. Uskova, O. V. and co-authors (2003). Programmirivaniye algoritmov obrabotki dannykh [Programming of algorithms for data processing]. S.-Petersburg, 102 p.
  16. Guzik, V. F., Zolotovskiy, V. E., Chinenkov, S. A. (1992). Organizatsiya razlichnykh metodov sortirovki v vychislitelnykh sistemakh [Organizing of different sorting methods in computing systems]. Elektronnoye modelirovaniye – Electrical modeling, vol. 14, no. 3, 25–28.
  17. Hea, M., Wua, X., Zhengb, S. Q. (2009). An optimal and processor efficient parallel sorting algorithm on a linear array with a reconfigurable pipelined bus system. Computers & Electrical Engineering, vol. 35, issue 6, 951–965.
  18. Knut, D. E. (2003). Iskusstvo programmirovaniya. Tom 3. Sortirovka i poisk [Art of programming. Vol. 3. Sorting and search]. Moscow, 832 p.
  19. Chandra, S., Jain, M., Basu, A., Kumar, P. S. (1993). Sorting algorithms on transputer arrays. Parallel Computing, vol. 19, issue 6, 595–607.
  20. Lin, Y.-C., Lin, F.-C. (1990). Parallel sorting with cooperating heaps in a linear array of processors. Parallel Computing, vol. 16, issue 2–3, 273–278.

Downloads

Published

2013-07-24

How to Cite

Мельничук, А. С., Луценко, С. П., Громовий, Д. С., & Трофимова, К. В. (2013). Analysis of methods for number array sorting. Technology Audit and Production Reserves, 4(1(12), 37–40. https://doi.org/10.15587/2312-8372.2013.16239

Issue

Vol. 4 No. 1(12) (2013): Technology audit and production reserves

Section

Technology audit

License

Copyright (c) 2016 Андрій Сергійович Мельничук, Сергій Петрович Луценко, Дмитро Сергійович Громовий, Карина Вікторівна Трофимова

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.