4

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)
  • Possible duplicate of how-can-i-rank-teams-based-off-of-head-to-head-wins-losses – candied_orange Jul 17 '16 at 7:22
  • I have trouble understanding what you're asking. It's perfectly common not to know an item's rank in advance. In what way is your problem different from the normal sorting or maximum-finding task? – Kilian Foth Jul 17 '16 at 13:09
  • @KilianFoth If by normal sorting you mean a traditional sorting algorithm (en.wikipedia.org/wiki/Sorting_algorithm), then the problem differs in that the ordering is unknown and can differ between users. The choice in ordering is subjective. My goal is to show the fewest pairs of items to a user to determine "their" ranking. – JesseBuesking Jul 18 '16 at 15:58
  • @CandiedOrange the question you link to asks how to determine the ranking given wins and losses. In a sense, I'm asking how to pick the matchups that lead to the wins and losses in the first place, with the added constraint of minimizing the total number of matchups. – JesseBuesking Jul 18 '16 at 16:01
  • Possibly useful tool to run quicksort using human comparisons: leonid.shevtsov.me/post/… – Craig Younkins Mar 4 '18 at 2:45
2

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.

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.

  • To simplify, I'm assuming there's a total ordering. However, comparing items two by two is inefficient if you do it naively. If you pick your items optimally, you can minimize the number of comparisons that are needed in order to totally rank your list. This is the core of my question, which is asking how to do this efficiently / what's this class of problems called. – JesseBuesking Jul 19 '16 at 3:37
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.