Number of the records: 1

Customary Behavior of Sorting Reals with Linear Time Complexity

SYSNO ASEP	0533287
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	Customary Behavior of Sorting Reals with Linear Time Complexity
Author(s)	Jiřina, Marcel (UIVT-O)_{SAI, RID}
Source Title	Proceedings of 2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE 2020). - Piscataway : IEEE, 2020 - ISBN 978-1-7281-6695-7
Pages	s. 268-271
Number of pages	4 s.
Publication form	Online - E
Action	MACISE 2020: International Conference on Mathematics and Computers in Science and Engineering /2./
Event date	18.01.2020 - 20.01.2020
VEvent location	Madrid
Country	ES - Spain
Event type	WRD
Language	eng - English
Country	US - United States
Keywords	sorting algorithm ; sorting reals ; linear time complexity ; countingsort
Subject RIV	JC - Computer Hardware ; Software
OECD category	Computer hardware and architecture
R&D Projects	LM2015068 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
Institutional support	UIVT-O - RVO:67985807
UT WOS	000635100900050
EID SCOPUS	85092691435
DOI	10.1109/MACISE49704.2020.00056
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2021

Number of the records: 1