Algorithm for ranking a list of items

algorithmsranking-systems

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?

Note:

  • 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)

Best Answer

Standard sorting is very much possible, and it is exactly what you should be doing here.

  • the problem differs in that the ordering is unknown

There is no difference. A standard sorting algorithm does not know the "rank" or "strength" of any of the items it is sorting ahead of time. In fact, it never knows it. All it knows is that there is a way of asking "does item A come before or after item B?". Typically this is done by means of a function that is called multiple times during sorting.

Since the aim of most sorting algorithms to minimise the number of comparisons, and you want to minimise the number of comparisons, you have your answer there. Moreover, if you don't want to order all the items but (say) find the top ten, there are well-known sorting algorithms that will do this as well.

It is true that in most cases discussed in textbooks, it is possible to answer "does A come before or after item B?" purely algorithmically, using information stored within A and B. All the examples you tend to see will assume this. But this is not essential. There is nothing wrong with a comparison function whose implementation is:

  1. Present A and B to the user.
  2. Ask the user which should come first.
  3. Return the user's answer to the sorting algorithm.

and such an function is exactly what you would be using here.

  • the problem differs in that the ordering… can differ between users

There is no difference here either. "Sorting according to Archibald's opinion" and "sorting according to Ermintrude's opinion" are two separate sorting operations, conducted separately on behalf of two separate users - just as "sorting according to weight" and "sorting according to height" are two separate sorting operations, conducted separately on two different sorting criteria.

Related Topic