Improved Results for Minimum-Comparison Selection,
Abstract
This report addresses the problem of selecting the Tth largest item in a collection of N items where the only tool allowed is that of comparing two items at a time to find which is larger. One can interpret this in terms of a set of objects with unknown weights where we can compare them two at a time on a balance scale, or as a tennis tournament where the abilities of the players are considered fixed, transitive and unequal. This problem of selection by comparisons is closely related to the broader problem of sorting data on a computer. Although there are other practical considerations such as storage, algorithmic complexity, etc., most theoretical discussions have been concerned with minimizing the number of comparisons which suffice either to sort data or to select, say, the median from an unsorted collection.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1974
- Accession Number
- AD0783272
Entities
People
- Selmer M. Johnson
Organizations
- RAND Corporation