Počet záznamů: 1
Customary Behavior of Sorting Reals with Linear Time Complexity
- 1.
SYSNO ASEP 0533287 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Customary Behavior of Sorting Reals with Linear Time Complexity Tvůrce(i) Jiřina, Marcel (UIVT-O) SAI, RID Zdroj.dok. Proceedings of 2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE 2020). - Piscataway : IEEE, 2020 - ISBN 978-1-7281-6695-7 Rozsah stran s. 268-271 Poč.str. 4 s. Forma vydání Online - E Akce MACISE 2020: International Conference on Mathematics and Computers in Science and Engineering /2./ Datum konání 18.01.2020 - 20.01.2020 Místo konání Madrid Země ES - Španělsko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova sorting algorithm ; sorting reals ; linear time complexity ; countingsort Vědní obor RIV JC - Počítačový hardware a software Obor OECD Computer hardware and architecture CEP LM2015068 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000635100900050 EID SCOPUS 85092691435 DOI 10.1109/MACISE49704.2020.00056 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2021
Počet záznamů: 1