A Criterion for Sorting Reals in a Linear Time

Authors: Marcel Jiřina
Publication year: 2022
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Proceedings of Seventh International Congress on Information and Communication Technology. ICICT 2022, London, Volume 4, Volume 4
Projects: Research Infrastructure for Fermilab Experiments
Bibliographic citation: JIŘINA, Marcel. A Criterion for Sorting Reals in a Linear Time. In: YANG, X.-S., SHERRATT, S., DEY, N., JOSHI, A., eds. Proceedings of Seventh International Congress on Information and Communication Technology. ICICT 2022, London, Volume 4, Volume 4. Singapore: Springer, 2022, S. 437-447. Lecture Notes in Networks and Systems, 465. ISBN 978-981-19-2396-8
Dostupné z: doi:10.1007/978-981-19-2397-5_41.
DOI: 10.1007/978-981-19-2397-5_41
ID: 556781
Online record: View online record

Abstract

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.