List sorting algorithm for comparisons done by humans

Question

This question was asked once before but not answered so I thought I would ask again with some specifics to my situation.

I am trying to develop an app that lets you put in a list of discrete items (for this example, fruit) and it offers you comparisons between two. You choose your favourite of the two and then this process repeats until eventually you have a list ordered by preference of these objects (in this example, a list of your favourite fruit, in order).

The issue is that traditional sorting strategies, no matter how fast, are going to necessarily involve more operations than is feasible for a human to do in any sensible amount of time (even with a list as short as 50, as my current test list is).

Since obviously there isn't a guaranteed sorting algorithm with low enough complexity, I guess some allowances have to made. Is there a way to skip out large chunks of sorting? I considered some way of assigning values to items based on the number of comparisons they've 'won' and then stopping the sort after a while and assuming that those values give the correct order, similar to the style that you might resolve a swiss chess tournament if you cant complete enough rounds to determine a winner normally. I dont know if that is plausible.

An example to clarify what I mean: say you had a list of

Apple
Orange
Kiwi
Banana
Melon

It would offer you comparisons like

Do you prefer:
A Apple
B Kiwi

and so on until you have a list that looks like

Kiwi
Apple
Orange
Melon
Banana

which is your order of preference of those fruit.

Answer 1

What are your fruit preferences? Do you have a full ordered list of preferences in your mind, or do you have fruits you "like more than most," fruits you "like less than most," and the rest which you don't have any strong feelings about - or you haven't even tried.

The problem with how you have formulated your problem is that you have assumed that a person's preferences are a total order, which is naturally encoded as a list. Really, a person's preferences are often a partial order, which is naturally encoded as a directed acyclic graph.

For example, for the set of fruits {Apple, Orange, Kiwi, Banana, Melon, Starfruit}, I might have fruit preferences as follows:

Melon < Apple
Apple < Banana
Banana < Kiwi
Banana < Orange

A good way to arrive at a partial order based on user input is to mimic radix sort. To start, ask the user to select, for each fruit, whether they like it, dislike it, feel neutral about it, or don't know. I would answer that as follows:

            Like Dislike Neutral Unknown
Apple                    x
Orange      x
Kiwi        x
Banana      x
Melon            x
Starfruit                        x

Assuming Dislike < Neutral < Like, these answers encode the following information, even though I've only answered as many questions as there are fruits:

Melon < Apple
Apple < Orange
Apple < Kiwi
Apple < Banana

Next, identify which answer(s) received the most check marks. In this case, I seem to have 3 fruits I like, 1 I dislike, and 1 I feel neutral about (unless peanut butter is involved), and 1 I've never tried (so I don't have any preference with respect to the other fruits).

So the natural place to further investigate my preferences would be within the fruits I like. The problem is recursive: now you want to determine my preferences in the set of fruits {Orange, Kiwi, Banana}. You could ask me which of those fruits are my favorite, and I'd click Orange and Kiwi. That tells you the following:

Banana < Orange
Banana < Kiwi

Combined with the first round of information, you now have:

Melon < Apple
Apple < Orange
Apple < Kiwi
Apple < Banana
Banana < Kiwi
Banana < Orange

Apple < Banana and Banana < Kiwi imply Apple < Kiwi; Apple < Banana and Banana < Orange imply Apple < Orange. So we can eliminate the redundant information to arrive at the following:

Melon < Apple
Apple < Banana
Banana < Kiwi
Banana < Orange

Answer 2

Use an insertion sort. Instead of asking the user to compare two items at a time, ask them to select their favorite from the entire remaining list. Put that item at the end of the sorted list, remove it from the remaining items, and repeat until the remaining items are exhausted.

Answer 3

You could let the user not only give whether an item is more preferable than another, but also a rating from 1 to 10 for example how much more he prefers the one from the other. That way you have more information and can easily create a ranking.

In the optimal approach where a user can only say smaller or bigger you need to perform binary search for each item in the list. Binary search has complexity O(log n). Doing this n times with n going from 1 to n makes a total of O(n * log (n/2)). In case of 50 items that would require a bit more than 200 steps.