Number of the records: 1
Nearly All Reals Can Be Sorted with Linear Time Complexity
- 1.
SYSNO ASEP 0544787 Document Type V - Research Report R&D Document Type The record was not marked in the RIV Title Nearly All Reals Can Be Sorted with Linear Time Complexity Author(s) Jiřina, Marcel (UIVT-O) SAI, RID Issue data Prague: ICS CAS, 2021 Series Technical Report Series number V-1285 Number of pages 22 s. Language eng - English Country CZ - Czech Republic Keywords sorting ; algorithm ; real sorting key ; time complexity ; linear complexity R&D Projects LM2015068 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) Institutional support UIVT-O - RVO:67985807 Annotation We propose a variant of the counting sort modified for sorting reals in a linear time. It is assumed that the sorting key and pointers to the items being sorted are moved and individual items remain at the same place in the memory (in place sorting). In this case, the space complexity of the new variant of the algorithm is the same as the complexity of the quicksort. We also quantify the practical limits for possible sorting reals in a linear time. This possibility is assured under additional assumptions 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. A new, faster version of the algorithm is attached. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2022
Number of the records: 1