The Library

Selection and sorting with limited storage

Tools

Munro, J. I. and Paterson, M. S. (1978) Selection and sorting with limited storage. Coventry, UK: Department of Computer Science..

Full text not available from this repository.

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 $K^{th}$ highest of N inputs. We show, for example, that to find the median in two passes requires at least $\Omega (N^{\frac{1}{2}})$ and at most $O(N^{\frac{1}{2}} log N)$ internal storage. For probabilistic methods, $O(N^{\frac{1}{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 > QA75 (Please use QA76 Electronic Computers. Computer Science)
Divisions: Faculty of Science > Computer Science
Publisher: Department of Computer Science
Place of Publication: Coventry, UK
Date: July 1978
Identification Number: CS-RR-024
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
Related URLs:
URI: http://wrap.warwick.ac.uk/id/eprint/46321

Request changes to a record

Actions (login required)

View Item View Item