An in-place sorting with O (n log n) comparisons and O (n) Moves

被引：9

作者：

Franceschini, G ^{[1
]}

Geffert, V ^{[1
]}

机构：

[1] Univ Pisa, Dept Comp Sci, I-56127 Pisa, Italy

来源：

44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2003年

关键词：

D O I：

10.1109/SFCS.2003.1238198

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e.g., in [J. L Munro and V Raman, Sorting with minimum data movement, J. Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.

引用

页码：242 / 250

页数：9

共 15 条

[1] ALGORITHM-245 - TREESORT 3 [M1]
FLOYD, RW
[J]. COMMUNICATIONS OF THE ACM, 1964, 7 (12) : 701 - 701
[2] FRANCESCHINI G, 2003, IN PLACE SORTING ALG
[3] Asymptotically efficient in-place merging
Geffert, V
Katajainen, J
Pasanen, T
[J]. THEORETICAL COMPUTER SCIENCE, 2000, 237 (1-2) : 159 - 181
[4] GEFFERT V, 2002, SORTING O N LOG N CO
[5] Itai A., 1981, LECTURE NOTES COMPUT, V115, P417
[6] Katajainen J., 1996, Nordic Journal of Computing, V3, P27
[7] In-place sorting with fewer moves
Katajainen, J
Pasanen, TA
[J]. INFORMATION PROCESSING LETTERS, 1999, 70 (01) : 31 - 37
[8] Knuth D. E., 1973, The Art of Computer Programming Volume 3, Sorting and Searching, VIII
[9] Selection from read-only memory and sorting with minimum data movement
Munro, JI
Raman, V
[J]. THEORETICAL COMPUTER SCIENCE, 1996, 165 (02) : 311 - 323
[10] MUNRO JI, 1992, J ALGORITHMS, V13, P374, DOI 10.1016/0196-6774(92)90045-E

← 1 2 →