A General Framework for Sorting Large Data Sets Using Independent Subarrays of Approximately Equal Length

IEEE Access

Shahriar Shirvani Moghaddam¹  Kiaksar Shirvani Moghaddam² 

[1] Faculty of Electrical Engineering, Shahid Rajaee Teacher Training University (SRTTU), Tehran, Iran;School of Computer Engineering, Iran University of Science and Technology (IUST), Tehran, Iran;

关键词: Data sorting;    Gaussian;    integer;    merge;    multi-core;    non-integer;   

DOI  :  10.1109/ACCESS.2022.3145981

来源: DOAJ

【 摘 要 】

Designing an efficient data sorting algorithm that requires less time and space complexity is essential for computer science, different engineering disciplines, data mining systems, wireless networks, and the Internet of things. This paper proposes a general low-complex data sorting framework that distinguishes the sorted or similar data, makes independent subarrays approximately in equal length, and sorts the subarrays’ data using one of the popular comparison-based sorting algorithms. Two frameworks, one for serial realization and another for parallel realization, are proposed. The time complexity analyses of the proposed framework demonstrate an improvement compared to the conventional Merge and Quick sorting algorithms. Following complexity analysis, the simulation results indicate slight improvements in the elapsed time and the number of swaps of the proposed serial Merge-based and Quick-based frameworks compared to the conventional ones for low/high variance integer/non-integer data sets, in different data sizes and the number of divisions. It is about $(1-1.6\%)$ to $(3.5-4\%)$ and $(0.3-1.8\%)$ to $(2-4\%)$ improvements in the elapsed times for 1, 2, 3, and 4 divisions, respectively for small and very large data sets in Merge-based and Quick-based scenarios. Although these improvements in serial realization are minor, making independent low-variance subarrays allows the sorted components to be extracted sequentially and gradually before the end of the sorting process. Also, it proposes a general framework for parallelizing conventional sorting algorithms using non-connected (independent) or connected (dependent) multi-core structures. As the second experiment, the numerical analyses that compare the results of the parallel realization of the proposed framework to the serial one in 1, 2, 3, and 4 divisions, show a speedup factor of $(2-4)$ for small to $(2-16)$ for very large data sets. The third experiment shows the effectiveness of the proposed parallel framework to the parallel sorting based on the random-access machine model. Finally, we prove that the mean-based pivot is as efficient as the median-based and much better than the random pivot for making subarrays of approximately equal length.

【 授权许可】

Unknown