Customary Behavior of Sorting Reals with Linear Time Complexity

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F20%3A00533287" target="_blank" >RIV/67985807:_____/20:00533287 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1109/MACISE49704.2020.00056" target="_blank" >http://dx.doi.org/10.1109/MACISE49704.2020.00056</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/MACISE49704.2020.00056" target="_blank" >10.1109/MACISE49704.2020.00056</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Customary Behavior of Sorting Reals with Linear Time Complexity
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Customary Behavior of Sorting Reals with Linear Time Complexity
Popis výsledku anglicky
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.

Projekt
<a href="/cs/project/LM2015068" target="_blank" >LM2015068: Výzkumná infrastruktura pro experimenty ve Fermilab</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Proceedings of 2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE 2020)
ISBN
978-1-7281-6695-7
ISSN
—
e-ISSN
—
Počet stran výsledku
4
Strana od-do
268-271
Název nakladatele
IEEE
Místo vydání
Piscataway
Místo konání akce
Madrid
Datum konání akce
18. 1. 2020
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000635100900050

Podobné výsledky(10)