Algorithm for ranking a list of items

Question

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)

Answer 1

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.

Answer 2

So you are looking for ranking items by minimizing pairwise comparison. It is exactly what standard sorting algorithm optimally does in O(n*ln(n)) comparison. (The proof of optimality is on text books such as Introduction of algorithms)

Concerning the problem of just having the first k elements sorted, it is called partial sorting and can be optimally solved in O(n*ln(k)) comparison. It is done by inserting in a heap the k first element then for the other elements in the heap inserting the element in the heap and removing the smallest element of the heap.

past edit

Assuming that there is no total order on your items, there is no perfect rank ordering for example there is no rank ordering which solve circular dependencies as A beat B which beat C which beat A.

If a total order exists classic algorithm perfectly works because in classic sort algorithm all you need is to be able to compare items two by two, no need to calculate a strength before hand.

In the case there is no total ordering, looks like you need to look towards tournament schedules, my best bet would be some derivate of swiss tournament to compromise number of comparison against the precision of a full round-robin tournament.

Answer 3

I'm not sure if this is exactly what you had in mind, but I just implemented an interactive O(n log n) sorting algorithm that relies on head-to-head comparisons. In pseudocode:

Create an empty self-balancing binary search Tree (I used a red-black tree).
Each tree node has a numeric Rank, a Value, and a potential Left and Right node.
For each item X being sorted:
  Establish Lower and Upper = undefined.
  Select the root tree node Node (if any).
  While Node exists:
    Y = Node.Value.
    Compare X and Y.
    If X < Y:
      Upper = Node.Rank
      Node = Node.Left
    Else:
      Lower = Node.Rank
      Node = Node.Right
  If Upper and Lower are not defined:
    Tree.insert(0, X)
  Else If Lower is not defined:
    Tree.insert(Upper - 1, X)
  Else If Upper is not defined:
    Tree.insert(Lower + 1, X)
  Else:
    Tree.insert((Upper + Lower) / 2, X)

In this algorithm, the Compare X and Y step is the interactive bit where you present the user the two choices. Because a binary tree is used, only log n comparisons are performed on an insert. The algorithm assumes that relative rankings are absolute/static, like if A < B and C < A, there's no reason to compare B and C.