The Library
Selection and sorting with limited storage
Tools
Tools
Tools
Munro, J. Ian and Paterson, Michael S. (1978) Selection and sorting with limited storage. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
|
Text
WRAP_Munro_cs-rr-024.pdf - Published Version Download (806Kb) | Preview |
Abstract
When selecting from, on sorting, a file stored on a
read-only tape and the internal storage is rather limited, several
passes of the input tape may be required. We study the relation
between the amount of internal storage available and the number of
passes required to select the Kth highest of N inputs. We show,
for example, that to find the median in two passes requires at
least Ω(N1/2) and at most O(N1/2 log N) internal storage. For probabilistic methods, O(N1/2) internal storage is necessary and sufficient for a single pass method which finds the median with high probability.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Data tapes -- Mathematical models | ||||
| Series Name: | Theory of Computation Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | July 1978 | ||||
| Dates: |
|
||||
| Number: | Number 24 | ||||
| Number of Pages: | 15 | ||||
| DOI: | CS-RR-024 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | M.S. Paterson and J.I. Munro, Selection and Sorting with Limited Storage, Theoretical Computer Science 12 (3), pp. 315-323 (1980) | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Date of first compliant deposit: | 1 August 2016 | ||||
| Date of first compliant Open Access: | 1 August 2016 | ||||
| Funder: | Science Research Council (Great Britain) (SRC) | ||||
| Version or Related Resource: | Paterson, M.S. and Munro, J.I. (1980). Selection and sorting with limited storage. Theoretical Computer Science, 12(3), pp. 315-323. |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
