Customary Behavior of Sorting Reals with Linear Time Complexity

0533287 - ÚI 2021 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Jiřina, Marcel
Customary Behavior of Sorting Reals with Linear Time Complexity.
Proceedings of 2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE 2020). Piscataway: IEEE, 2020, s. 268-271. ISBN 978-1-7281-6695-7.
[MACISE 2020: International Conference on Mathematics and Computers in Science and Engineering /2./. Madrid (ES), 18.01.2020-20.01.2020]
Grant CEP: GA MŠMT LM2015068
Institucionální podpora: RVO:67985807
Klíčová slova: sorting algorithm * sorting reals * linear time complexity * countingsort
Obor OECD: Computer hardware and architecture

Sorting with real number keys has time complexity n log n. This holds under the assumption that for all n samples a comparison sort is used. Here we propose to use the counting sort with just n cells for initial placement of samples. We resolve cases of groups of several samples placed into one cell by a comparison sort. Surprisingly, even this part has time complexity proportional to n. Numerical experiments confirm this finding and shows influence of the computing environment such as paging, and reflects a higher speed than the quicksort.
Trvalý link: http://hdl.handle.net/11104/0311712