MESH SORTING AND SELECTION OPTIMAL ON THE AVERAGE

Authors
CHLEBUS BS
Citation
Bs. Chlebus, MESH SORTING AND SELECTION OPTIMAL ON THE AVERAGE, Computers and artificial intelligence, 16(2), 1997, pp. 141-152
Citations number
17
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence
Journal title
Computers and artificial intelligence → ACNP
ISSN journal
02320274
Volume
16
Issue
2
Year of publication
1997
Pages
141 - 152
Database
ISI
SICI code
0232-0274(1997)16:2<141:MSASOO>2.0.ZU;2-E
Abstract
We consider 1-1 sorting and selection problems on an n x n mesh-connec ted processor arrays. Algorithms are developed which are fast with res pect to the average-time performance. We show that selection can be ac complished in the average time n + o(n), and sorting in the average ti me 2.n + o(n). Matching lower bounds are also proved.