Bicomponent sorting algorithms

V. I. Shynkarenko, A. Yu. Doroshenko, O. A. Yatsenko, V. V. Raznosilin, K. K. Halanin

Abstract


The possibilities of improving sorting time parameters through preprocessing by stochastic sorting were investigated. The hypothesis that two-component stochastic + classical sorting outperforms classic one-component sorting in terms of time efficiency was experimentally confirmed. Sorting with different computational complexity is accepted as classical sorting algorithms: shaker sort- ing with computational complexity O(n2), insertions O(n2), Shell O(n·(log n)2) ... O(n3/2), fast with optimization of ending sequences O(n·log n). The greatest effect is obtained when performing comparisons using stochastic sorting in the amount of 160 percent of the array’s size. Indicators of the efficiency of the exchange of two elements, as well as series of exchanges, are introduced. This allowed to determine the highest efficiency of stochastic sorting (as the first component of two-component sorting), when one element for comparison is chosen from the first part of the array and the other from the second. For algorithms with a computational complexity of O(n2) the improvement in time efficiency reached 70–80 percent. However, for Shell sort and quick sort, the stochas- tic presort has no positive effect, but instead increases the total sorting time, which is apparently due to the initial high efficiency of these sorting methods. The hypothesis that three-component sorting fast + stochastic + insertions would increase sorting time efficiency was not confirmed. However, during the experiment, the recommended size of the array was determined, at which point the two-component quick + insertion sort must be switched to the second component – insertion sorting. The optimal length of the ending sequences is between 60 and 80 elements. Given that algorithm time efficiency is affected by computer architecture, operat- ing system, software development and execution environment, data types, data sizes, and their values, time efficiency indicators should be specified in each specific case.

Problems in programming 2022; 3-4: 32-41


Keywords


sorting; stochastic sorting; algorithm; time efficiency; experiment

References


SHYNKARENKO, V., ILCHENKO, P. & ZABULA, H. (2018) Tools of investigation of time and functional efficiency of bionic algo- rithms for function optimization problems. In International Conference of Programming. Kyiv, Tuesday 22th to Thursday 24th May 2018. CEUR Workshop Proceedings. 2139. p. 270-280.

CORMEN, T. H. et al. (2009) Introduction To Algorithms (3rd ed.). Cambridge, MA: The MIT Press, 1292 p.

YADAV, R., YADAV, R. & GUPTA, S. B. (2021). Comparative study of various stable and unstable sorting algorithms. Artificial Intel- ligence and Speech Technology. CRC Press. CrossRef

WIKIPEDIA. (2022) Sorting algorithm. [Online] July 2022. Available from: URL: https://en.wikipedia.org/wiki/Sorting_algorithm [Accessed: 11th July 2022].

KNUTH, D. (1973) The Art of Programming, Vol. 3 Sorting and Searching.

MUBARAKA, A., IQBALB, S., NAEEMC, T. & HUSSAIND S. (2022) 2 mm: a new technique for sorting data. Theoretical Computer Science. 910. p. 68-90. CrossRef

THABIT, K. & BAWAZIR, A. A (2013) Novel approach of selection sort algorithm with parallel computing and dynamic programing concepts. Journal of King Abdulaziz University Computing and Information Technology Sciences. 2. p. 27-44. CrossRef

YATSENKO, O. (2011) On application of machine learning for development of adaptive sorting programs in algebra of algorithms. Proc. Int. Workshop "Concurrency: Specification and Programming" (CS&P'2011). Pułtusk, Poland, 28-30 September 2011. Bialystok: Bialystok University of Technology. p. 577-588.

DOROSHENKO, A. & YATSENKO, O. (2021) Formal and Adaptive Methods for Automation of Parallel Programs Construction: Emerging Research and Opportunities. Hershey: IGI Global. CrossRef

DOROSHENKO, A. et al. (2019) A mixed method of parallel software auto-tuning using statistical modeling and machine learning. Communications in Computer and Information Science. Information and Communication Technologies in Education, Research, and Industrial Applications. 1007. p. 102-123. CrossRef

DURRANI, O. K., SHREELAKSHMI, V., SHETTY, S. & VINUTHA, D. C. (2018) Analysis and determination of asymptotic behavior range for popular sorting algorithms. Special Issue of International Journal of Computer Science & Informatics. 2(1). p. 149-154.

DRĂMNESC, I., JEBELEAN, T. & STRATULAT, S. (2019). Mechanical synthesis of sorting algorithms for binary trees by logic and combinatorial techniques. Journal of Symbolic Computation. 90. p. 3-41. CrossRef

MICROSOFT DOCUMENTS. (2022) VirtualAlloc function. [Online] May 2022. Available from: https://docs.microsoft.com/en-us/win- dows/win32/api/memoryapi/nf-memoryapi-virtualalloc [Accessed: 11th July 2022].

FRAK, A. N. et al. Comparison study of sorting techniques in static data structure. International Journal of Integrated Engineering: Special Issue Data Information Engineering. 10(6). p. 106-112.

KUSHAGRA, S., LÓPEZ-ORTIZ, A., QIAO, A. & MUNRO, J. I. (2014) Multi-pivot quicksort: theory and experiments. In Workshop on Algorithm Engineering and Experiments. Portland, Oregon, USA, Sunday 5th January 2014, p. 47-60. CrossRef

MANSI R. (2010) Enhanced quicksort algorithm. International Arab Journal of Information Technology. 7(2). p. 161-166.

AFTAB, A. et al. (2021) Review on performance of quick sort algorithm. International Journal of Computer Science and Information Security. 19(2). p. 114-120.

WOŹNIAK, M. et al. (2016) Preprocessing large data sets by the use of quick sort algorithm. In Knowledge, Information and Creativity Support Systems: Recent Trends, Advances and Solutions. Springer. CrossRef




DOI: https://doi.org/10.15407/pp2022.03-04.032

Refbacks

  • There are currently no refbacks.