Improved Results for Minimum-Comparison Selection,
RAND CORP SANTA MONICA CALIF
Pagination or Media Count:
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.
- Computer Programming and Software