Comparing algorithms for sorting with t stacks in series
| dc.creator | Smith, Rebecca | |
| dc.date | 2004-04-08 | |
| dc.date | 2004-06-18 | |
| dc.date.accessioned | 2026-07-07T05:07:17Z | |
| dc.date.available | 2026-07-07T05:07:17Z | |
| dc.description | We show that the left-greedy algorithm is a better algorithm than the right-greedy algorithm for sorting permutations using t stacks in series when t>1. We also supply a method for constructing some permutations that can be sorted by t stacks in series and from this get a lower bound on the number of permutations of length n that are sortable by t stacks in series. Finally we show that the left-greedy algorithm is neither optimal nor defines a closed class of permutations for t>2. | |
| dc.description | 9 pages, 7 figures, To be published in Annals of Combinatorics. The new version makes a few grammatical changes, clarifies a definition, and fixes the figures | |
| dc.identifier | https://arxiv.org/abs/math/0404176 | |
| dc.identifier | http://arxiv.org/abs/math/0404176 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70800 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A05 (primary), 68R05, 68W01 (secondary) | |
| dc.title | Comparing algorithms for sorting with t stacks in series | |
| dc.type | text |