On the Performance of Mean-Based Sort for Large Data Sets
Computer and communication systems and networks deal with many cases that require rearrangement of data either in descending or ascending order. This operation is called sorting, and the purpose of an efficient sorting algorithm is to reduce the computational complexity and time taken to perform the...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9366731/ |
| _version_ | 1798001953324662784 |
|---|---|
| author | Shahriar Shirvani Moghaddam Kiaksar Shirvani Moghaddam |
| author_facet | Shahriar Shirvani Moghaddam Kiaksar Shirvani Moghaddam |
| author_sort | Shahriar Shirvani Moghaddam |
| collection | DOAJ |
| description | Computer and communication systems and networks deal with many cases that require rearrangement of data either in descending or ascending order. This operation is called sorting, and the purpose of an efficient sorting algorithm is to reduce the computational complexity and time taken to perform the comparison, swapping, and assignment operations. In this article, we propose an efficient mean-based sorting algorithm that sorts integer/non-integer data by making approximately the same length independent quasi-sorted subarrays. It gradually finds sorted data and checks if the elements are partially sorted or have similar values. The elapsed time, the number of divisions and swaps, and the difference between the locations of the sorted and unsorted data in different samples demonstrate the superiority of the proposed algorithm to the Merge, Quick, Heap, and conventional mean-based sorts for both integer and non-integer large data sets which are random or partially/entirely sorted. Numerical analyses indicate that the mean-based pivot is appropriate for making subarrays with approximately similar lengths. Also, the complexity study shows that the proposed mean-based sorting algorithm offers a memory complexity same as the Quick-sort and a time complexity better than the Merge, Heap, and Quick sorts in the best-case. It is similar to the Merge and Heap sorts in view of the time complexity of the worst-case much better than the Quick-sort while these algorithms experience identical complexity in the average-case. In addition to finding part by part incremental (or decremental) sorted data before reaching the end, it can be implemented by parallel processing the sections running at the same time faster than the other conventional algorithms due to having independent subarrays with similar lengths. |
| first_indexed | 2024-04-11T11:44:28Z |
| format | Article |
| id | doaj.art-6aa15e98041a4fbdbfb5376051fab21f |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-11T11:44:28Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-6aa15e98041a4fbdbfb5376051fab21f2022-12-22T04:25:40ZengIEEEIEEE Access2169-35362021-01-019374183743010.1109/ACCESS.2021.30632059366731On the Performance of Mean-Based Sort for Large Data SetsShahriar Shirvani Moghaddam0https://orcid.org/0000-0002-8427-2446Kiaksar Shirvani Moghaddam1https://orcid.org/0000-0003-0249-1547Faculty of Electrical Engineering, Shahid Rajaee Teacher Training University, Tehran, IranSchool of Computer Engineering, Iran University of Science and Technology, Tehran, IranComputer and communication systems and networks deal with many cases that require rearrangement of data either in descending or ascending order. This operation is called sorting, and the purpose of an efficient sorting algorithm is to reduce the computational complexity and time taken to perform the comparison, swapping, and assignment operations. In this article, we propose an efficient mean-based sorting algorithm that sorts integer/non-integer data by making approximately the same length independent quasi-sorted subarrays. It gradually finds sorted data and checks if the elements are partially sorted or have similar values. The elapsed time, the number of divisions and swaps, and the difference between the locations of the sorted and unsorted data in different samples demonstrate the superiority of the proposed algorithm to the Merge, Quick, Heap, and conventional mean-based sorts for both integer and non-integer large data sets which are random or partially/entirely sorted. Numerical analyses indicate that the mean-based pivot is appropriate for making subarrays with approximately similar lengths. Also, the complexity study shows that the proposed mean-based sorting algorithm offers a memory complexity same as the Quick-sort and a time complexity better than the Merge, Heap, and Quick sorts in the best-case. It is similar to the Merge and Heap sorts in view of the time complexity of the worst-case much better than the Quick-sort while these algorithms experience identical complexity in the average-case. In addition to finding part by part incremental (or decremental) sorted data before reaching the end, it can be implemented by parallel processing the sections running at the same time faster than the other conventional algorithms due to having independent subarrays with similar lengths.https://ieeexplore.ieee.org/document/9366731/Ascendingdescendingdivide-and-conquerheapintegerlarge data set |
| spellingShingle | Shahriar Shirvani Moghaddam Kiaksar Shirvani Moghaddam On the Performance of Mean-Based Sort for Large Data Sets IEEE Access Ascending descending divide-and-conquer heap integer large data set |
| title | On the Performance of Mean-Based Sort for Large Data Sets |
| title_full | On the Performance of Mean-Based Sort for Large Data Sets |
| title_fullStr | On the Performance of Mean-Based Sort for Large Data Sets |
| title_full_unstemmed | On the Performance of Mean-Based Sort for Large Data Sets |
| title_short | On the Performance of Mean-Based Sort for Large Data Sets |
| title_sort | on the performance of mean based sort for large data sets |
| topic | Ascending descending divide-and-conquer heap integer large data set |
| url | https://ieeexplore.ieee.org/document/9366731/ |
| work_keys_str_mv | AT shahriarshirvanimoghaddam ontheperformanceofmeanbasedsortforlargedatasets AT kiaksarshirvanimoghaddam ontheperformanceofmeanbasedsortforlargedatasets |