|
Home
|
Back to issue
|
ISSN 0474-8662. Information Extraction and Processing. 2019. Issue 47 (123)
Acceleration of large integer arrays sorting using ranges of values and frequencies of elements
Shportko A.V.
Academician Stepan Demianchuk International University
of Economics and Humanities, Rivne
Shportko L. V.
Rivne College of Economics and Business, Rivne
https://doi.org/10.15407/vidbir2019.47.073
Keywords: sorting of arrays, QuickSort sorting method, range of array elements values, sorting by counting
Cite as: Shportko A.V., Shportko L. V. Acceleration of large integer arrays sorting using ranges of values and frequencies of elements. Information Extraction and Processing. 2019, 47(123), 73-79. DOI:https://doi.org/10.15407/vidbir2019.47.073
Abstract
The speed of sorting of various types of large integer arrays by popular algorithms of different groups of methods is analyzed. As a result, the algorithm of rapid exchange sorting with parti-tioning and moving of the supporting element QuickSort has again been recognized as the most effective. An alternative algorithm for partitioning of the QuickSort method in relation to the half the range of values of the elements of each submachine, which makes it possible to use sorting by narrow ranges, is given. It is shown that subarrays with the length of up to 10 eleŽments should be sorted by simple inserts. For longer subarrays, if the range of values does not exceed its size, it is advisable to use the sorting method by counting. Otherwise, it is necessary to perform the iteration of the QuickSort method with a split in half the range of values of its elements. It has been experimentally proved that such a complex use of methods accelerates, for example, sorting of arrays with 1 million elements and with the range of values no more than 1000 by 34%. The results obtained can be used to accelerate the sorting of large integer arrays with the known or defined ranges of values.
References
1. Knuth, D. E. The Art of Computer Programming. Sorting and Searching, 2rd ed.; Massachusetts: Addison Wesley Longman, 1997; Vol. 3; p 791.
2. Williams, J. W. Algorithm 232 - Heapsort. Communications of the ACM 1964, 7 (6), 347-348.
3. Shell, D. L. A high-speed sorting procedure. Communications of the ACM 1959, 2 (7), 30-32.
https://doi.org/10.1145/368370.368387
4. Hoare, C. A. R. Quicksort. The Computer Journal 1962, 5 (1), 10-16.
https://doi.org/10.1093/comjnl/5.1.10
5. Cormen, T. H, Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms, 3rd ed.; Moscow: Williams, 2013; p 1328; (In Ru.).
6. Quick sort http://algolist.manual.ru/sort/quick sort.php (accessed by Jun 05, 2019) (In Ru.).
7. Quicksort - Wikipedia https://en.wikipedia.org/wiki/Quicksort (accessed by Jun 05, 2019).
8. Vlasyuk, A. P. Practical Programming Work in the Environment of Turbo Pascal; Rivne: NUWEE, 2005; Part.1; p 179 (In Ukr.).
9. C# Language Specification. Standard ECMA-334, 5-ed.; ECMA International, 2017.