AN OPTIMAL PARALLEL ADAPTIVE SORTING ALGORITHM

被引：3

作者：

CARLSSON, S

CHEN, JS

机构：

[1] Department of Computer Science, Lund University, S-221 00 Lund

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 39卷 / 04期

关键词：

PARALLEL ALGORITHMS; SORTING; PRESORTEDNESS;

D O I：

10.1016/0020-0190(91)90179-L

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the problem of designing optimal parallel algorithms for sorting presorted sequences. To evaluate the existing order in an input sequence, we use the number of the maximal ascending consecutive subsequences, Runs, in the sequence as a measure of presortedness. An adaptive parallel sorting algorithm is presented, which sorts a sequence X of length n in O(log n.log Runs (X)) time by using O(n/log n) processors in the EREW PRAM model of computation. It is the first adaptive parallel sorting algorithm that is cost optimal with respect to Runs.

引用

页码：195 / 200

页数：6

共 18 条

[1] SORTING IN C LOG N PARALLEL STEPS
AJTAI, M
KOMLOS, J
SZEMEREDI, E
[J]. COMBINATORICA, 1983, 3 (01) : 1 - 19
[2] SORTING ROUGHLY SORTED SEQUENCES IN PARALLEL
ALTMAN, T
CHLEBUS, BS
[J]. INFORMATION PROCESSING LETTERS, 1990, 33 (06) : 297 - 300
[3] ADAPTIVE BITONIC SORTING - AN OPTIMAL PARALLEL ALGORITHM FOR SHARED-MEMORY MACHINES
BILARDI, G
NICOLAU, A
[J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (02) : 216 - 228
[4] CHEN J, 1991, 2ND P ANN ACM SIAM S, P62
[5] PARALLEL MERGE SORT
COLE, R
[J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (04) : 770 - 785
[6] BEST SORTING ALGORITHM FOR NEARLY SORTED LISTS
COOK, CR
KIM, DJ
[J]. COMMUNICATIONS OF THE ACM, 1980, 23 (11) : 620 - 624
[7] SMOOTHSORT, AN ALTERNATIVE FOR SORTING INSITU
DIJKSTRA, EW
[J]. SCIENCE OF COMPUTER PROGRAMMING, 1982, 1 (03) : 223 - 233
[8] EXPLOITING PARTIAL ORDER WITH QUICKSORT
DROMEY, RG
[J]. SOFTWARE-PRACTICE & EXPERIENCE, 1984, 14 (06) : 509 - 518
[9] A NEW MEASURE OF PRESORTEDNESS
ESTIVILLCASTRO, V
WOOD, D
[J]. INFORMATION AND COMPUTATION, 1989, 83 (01) : 111 - 119
[10] Knuth D.E., 1997, ART COMPUTER PROGRAM, V3

← 1 2 →