Given a list of items, what's the most efficient way of ranking those items with the least number of comparisons? Is there a name for this type of algorithm (that way I can focus my search)?
Also, is there a way to do this and receive a partially completed ranking in order (1st, 2nd, etc) that's still near-optimal in the number of comparisons made? This way a user can stop choosing winners for pairs of items somewhere before the list has been total ranked, and know the top N items.
For example, say I have 8 items. I'd like to know the ranking of those items by giving two at a time to a user and having them compare the items. What's the most efficient way of having them rank the items by showing them the fewest number of pairs?
I know that, for a list of 8 items, it would take at most 7 comparisons to find the winner. You could find this by completing a bracket tournament (4 pairs round 1, 2 pairs round 2, 1 pair round 3). With 2 more comparisons, you would know who is 2nd (of the 3 opponents to 1st, two rounds to find who would have been 2nd). Is there an algorithm or class of them that solves these types of problems?
- Standarding sorting is not possible because we don't know an items "strength" or "rank" ahead of time.
- Ranking algorithms like ELO don't seem to solve this, as they don't tell you which matchups are required to find a total ranking with a minimal number of matchups. (I might be wrong here, but this seems to be the case)