Suppose I have m items, and I wish to ascertain their complete rank order 1..m using only paired comparisons and the minimum, on average, number of paired comparisons at that. I can do the comparisons sequentially ie knowing the results of all prior tests.

I am looking for an algorithm and some understanding of its optimality or otherwise.

As an example suppose I have seven items and the test sequence goes like this (a,b comparison >> winner)
1,2 >> 2
3,4 >> 3
5,6 >> 6
7 has not been tested yet.
If I introduce the concept of "possibly informative comparisons" now,
we have remaining
1,3
1,4
1,6
1,7
2,3
2,4
2,5
2,6
2,7
etc etc
But testing 2,3 (winner against winner) means that if 3 is the winner then we never need test 1,3 although we will have to test 2,4

So, there should be some gains (I think) in testing winner against winner (and then loser of that against previous winner etc).

I am sure this is well trodden ground, and I would appreciate any pointers to set me on the right path.

I would also be interested in extensions to the problem eg if we are interested in establishing only the top k ranks, and don't care about the rest.

I am also interested in the algorithmics, how I would write it in code. One idea I have is to start with all the items on a number line with upper and lower possible bounds : a test would then serve to shrink the bounds and/or make them non overlapping.

Sorry for the woolly thinking here, I am just feeling my way.

Any help would be greatly appreciated.

>Suppose I have m items, and I wish to ascertain their
>complete rank order 1..m using only paired comparisons and
>the minimum, on average, number of paired comparisons at
>that. I can do the comparisons sequentially ie knowing the
>results of all prior tests.
>
>I am looking for an algorithm and some understanding of its
>optimality or otherwise.

This is basically a sorting problem. There are various known algorithms for this, from bubble-sort (very simple to understand but very slow) to quick-sort (currently, as far as I know, tied with several other algorithms for fastest execution).

Quick-sort is a very easy to understand algorithm. Basically, you start with your m items in their initial order, and assign them initial position numbers 1 through m (the easy way to do this is to simply store the values of the items in an array, so the array index is their number). You then pick an item at random (called the pivot) and compare everything else to it to produce two subarrays, one with everything smaller and the other with everything larger than the given element.

You now have a situation where every element in the first array is known to be smaller than every element of the second array, so it is never necessary to compare them with each other again. Therfore the problem breaks down into tow smaller problems, namely sorting each of the subarrays. Now quick-sort calls ITSELF on each of the sub-arrays. Eventually all the sub-arrays have size one and the algorithm exits. At this point, every element must pretty obviously be in its correct place.

It is a very recursive algorithm, as you can see. This structure is very similar to the algorithmic structure of the Fast Fourier Transform algorithm, and accounts for its very good execution time. It is called a "divide and conquer" algorithm. Quick-sort performs m/2 swaps (on average) and then calls two copies of itself, which each perform m/4 swaps, for a total of another m/2, and then 4 copies of itself are called, each performing m/8 swaps, again for a total of another m/2, and so on. Each level of subroutine makes m/2 swaps, and there are at most log_2(m) levels of calling. Hence the total number of swaps averages to (m/2)log_2(m), which is very good indeed.

As far as I am aware, it is not known whether a faster algorithm can exist (someone correct me if I am wrong), but this is the currently fastest known algorithm that works for general m. For specific cases, such as the m=7 example you give, there can of course be faster sorting tricks, but they will only work for that specific value of m.

Here is a link to somebody else's Description of quick-sort. His discussion is good, but he is wrong about it being hard to program. The first time I heard about it, I sat down and make a working program in about 15 minutes. He mentions that sometimes the behavior of quick-sort is not very good, because if the data is already nearly ordered and you pick the first item in the list as the pivot, it runs in n^2 time, the same as bad old bubble-sort.

There is a way to avoid this by thinking about how numbers are represented in your data set. Suppose you are using unsigned integer data. In that case, you can avoid the pivot idea altogether: just sort the list on the highest bit into two sublists with initial bit 0 and initial bit 1, then sort each of the sublists on the second bit, and so on.

What if the numbers are signed integers? Then if they are stored in sign_magnitude format (not common!) sort on the first bit (0 means positive and 1 means negative in this format) and then sort the positive sublist just like the unsigned integers, and sort the negative list in reverse order. If they are stored in 2's complement (which is almost universally used) the bit complementing process fixes up the order of the negative numbers for you automatically, and so you can sort these exactly like unsigned integers.

If they are floating point, the exponent is usually stored in sign_magnitude and the rest of the digits in 2's complement. The first digit is the mantissa sign, and the second digit is the exponent sign. In this case, sort on the first bit, then on the second bit, then on the exponent bits (sort the sublist with negative exponent in reverse order) then on the mantissa bits (in the normal order).

This implementation depends on knowing the data format of your numbers, but it is never slower than quick-sort and has much better worst-case behavior, because you can't run into the badly chosen pivot problem. It has the advantage that you can produce the sublists by simply swapping the elements of the array in place, without creating new arrays to hold the subarrays.

You make pointers FIRST and LAST to the first and last array elements and call sort(FIRST,LAST). Inside sort() you first check if FIRST = LAST and exit if so. Then save them as FIRST_0 and LAST_0, then decrement FIRST and increment LAST until FIRST points to an element with the current sort bit = 1 and LAST points to an element with bit = 0. Swap those two elements and continue moving the pointers until FIRST = LAST-1. Now FIRST points to the last element of the subarray with bit 0 and LAST points to the first element of the subarray with bit 1. At this point, sort() calls sort(FIRST_0,FIRST) to sort the subarray with bit 0, and calls sort(LAST,LAST_0) to sort the subarray with bit 1.

This still uses a lot of stack for the recursive calls, but it's all pointers into the same data array, and so it never steps outside the originally allocated space. As you might be able to tell from the level of detail I went into here, this implementation of quick-sort is my own innovation, and I can't resist talking just a little too much about it. Just ignore it if it's beyond the scope of your question.

Hope this helps!

--Stuart Anderson