Back to Search
Start Over
Sorting with networks of data structures
- Source :
- Discrete Applied Mathematics. 158(15):1579-1586
- Publication Year :
- 2010
- Publisher :
- Elsevier BV, 2010.
-
Abstract
- We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time @Q(n^2) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time @W(n^3^/^2), and that there exist graphs of k nodes which can sort in time @Q(nlog"kn), which is optimal.
- Subjects :
- Discrete mathematics
Sorting algorithm
Comparison sort
Applied Mathematics
Combinatorics
Indifference graph
Chordal graph
Integer sorting
Permutation graph
Discrete Mathematics and Combinatorics
Counting sort
Pigeonhole sort
Computer Science::Databases
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 158
- Issue :
- 15
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....89475bfb4b0d0a2ddf9b4e0150037e4f
- Full Text :
- https://doi.org/10.1016/j.dam.2010.06.007