In-Place Sorting

被引：0

作者：

Geffert, Viliam ^{[1
]}

Gajdos, Jozef ^{[2
]}

机构：

[1] Safarik Univ, Dept Comp Sci, Jesenna 5, Kosice 04154, Slovakia

[2] Coll Internatl Business ISM Slovakia, Presov, Slovakia

来源：

SOFSEM 2011: THEORY AND PRACTICE OF COMPUTER SCIENCE | 2011年 / 6543卷

关键词：

in-place algorithms; sorting; computational complexity; MINIMUM DATA MOVEMENT; LOG N COMPARISONS; O(N) MOVES; SELECTION;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present an algorithm for asymptotically efficient sorting. Our algorithm sorts the given array A by the use of n.lg n + O(n.lg lg n) comparisons and O(n) element moves. Moreover, this algorithm works in-place, using only a constant auxiliary workspace. This shrinks the gap between the known information-theoretic lower bound and the existing algorithms to O(n/lg lg n) comparisons, even if we require the algorithm to use only a constant auxiliary memory and a linear number of moves.

引用

页码：248 / 259

页数：12

共 9 条

[1] An in-place sorting with O (n log n) comparisons and O(n) moves [J].

Franceschini, G ;

Geffert, V .

JOURNAL OF THE ACM, 2005, 52 (04) :515-537

[2] Sorting stably, in place, with O (n log n) comparisons and O(n) moves [J].

Franceschini, Gianni .

THEORY OF COMPUTING SYSTEMS, 2007, 40 (04) :327-353

[3]

Geffert V, 2006, COMPUT INFORM, V25, P333

[4]

Knuth D., 1998, ART COMPUTER PROGRAM

[5]

Knuth Donald E., 1998, The Art of Computer Programming, V3

[6] Selection from read-only memory and sorting with minimum data movement [J].

Munro, JI ;

Raman, V .

THEORETICAL COMPUTER SCIENCE, 1996, 165 (02) :311-323

[7]

MUNRO JI, 1992, J ALGORITHMS, V13, P374, DOI 10.1016/0196-6774(92)90045-E

[8]

Willard Dan E, 1982, P 14 ANN ACM S THEOR, P114

[9]

[No title captured]

← 1 →