Mesh Sorting and Selection Optimal to the Average
B. S. Chlebus
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
We consider 1-1 sorting and selection problems on an n x n mesh-connected processor arrays. Algorithms are developed which are fast with respect to the average-time performance. We show that selection can be accomplished in the average time 2-n + o(n), and sorting in the average time 2 . n+o(n). Matching lower bounds are also proved.
Publié le : 2012-01-26
Classification:  
@article{cai665,
     author = {B. S. Chlebus},
     title = {Mesh Sorting and Selection Optimal to the Average},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai665}
}

B. S. Chlebus. Mesh Sorting and Selection Optimal to the Average. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai665/