Quick relative ranking algorithm

Question

Let's say I own 100 video games, and I want to order them from most liked to least liked. It's very hard to give each video game a numeric value that represents how much I like it, so I thought of comparing them to each other.

One solution I came up with is picking 2 random video games, and selecting which one I liked more, and discarding the other one. Unfortunately this solution only lets me know the #1 video game since that would be the last one remaining, and provides little information about the others. I could then repeat the process for the other 99 video games, and so on but that is very impractical: O(n^2).

Are there any O(n) (or just reasonable) algorithms that can be used to sort data based on relative criteria?

Answer 1

If you want to present the games in a sequential order, you need to decide upon it.

It is possible to derive a sequential order from a set of pairwise comparisons.

Here is an example. You have 100 video games. We assume that every video game is associated with a parameter a_i (where i ranges from 1 to 100). It is a real number that describes how "much" you like the game. We don't know the values of those parameters yet. We then choose a function that describes how likely it is that you prefer video game i over video game j in terms of the parameters. We choose the logistic curve and define

P[i preferred over j] = 1/(1+e^{a_j - a_i})

Now when a_i = a_j you have P = 0.5, and when, say, a_i = 1 and a_j = 0 you have P = 1/(1 + e_-1) = 0.73, showing that a relative higher parameter values increases the probability that the corresponding video game is preferred.

Now then, when you have your actual comparison results in a table, you use the method of maximum likelihood to calculate the actual values for the parameters a_i. Then you sort your video games in descending order of the calculated parameters.

What happens is that the maximum likelihood method calculates those values for the parameters a_i that make the actual observed preferences as likely as possible, so the calculated parameters represent the best guess about a total ordering between the video games. Note that for this to work, you need to compare video games to other video games enough many times---every game needs at least one comparison, and the comparisons cannot form disjoint subsets (e.g. you compare A to B to C to A, and D to E to F to D, but there is no comparison between a game from {A,B,C} and a game from {D,E,F}).

Answer 2

You could use quicksort aka pivot sort. Pick a game, and compare every other game to it, so you have a group of worse game and better games. Repeat for each half recursively. Average case performance is n log n.

http://en.wikipedia.org/wiki/Quicksort