Accession Number : AD0783272

Title :   Improved Results for Minimum-Comparison Selection,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Johnson,Selmer M.

Report Date : JUN 1974

Pagination or Media Count : 44

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.

Descriptors :   *Computer programming, *Sorting, Recursive functions, Computations, Graphics, Selection

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE