A Criterion for Sorting Reals in a Linear Time

0556781 - ÚI 2023 RIV SG eng C - Conference Paper (international conference)
Jiřina, Marcel
A Criterion for Sorting Reals in a Linear Time.
Proceedings of Seventh International Congress on Information and Communication Technology. ICICT 2022, London, Volume 4, Volume 4. Singapore: Springer, 2022 - (Yang, X.; Sherratt, S.; Dey, N.; Joshi, A.), s. 437-447. Lecture Notes in Networks and Systems, 465. ISBN 978-981-19-2396-8.
[ICICT 2022: International Congress on Information and Communication Technology /7./. London / Virtual (GB), 21.02.2022-24.02.2022]
R&D Projects: GA MŠMT LM2015068
Institutional support: RVO:67985807
Keywords : sorting reals * counting sort * time complexity * space complexity
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://dx.doi.org/10.1007/978-981-19-2397-5_41

We quantify the practical limits for sorting reals in a linear time. This possibility is assured under assumption on the distribution of the sorting key, mainly the independence and identity of the distribution. Here we give a more general criteria easily applicable in practice. We also show that the algorithm is applicable for data that do not fulfill criteria for linear time complexity but even that the computation is faster than the system quicksort.
Permanent Link: http://hdl.handle.net/11104/0330977