List sorting algorithm for comparisons made by people

Question

This question was asked once before, but did not answer, so I thought that I would ask again with some features of my situation.

I am trying to develop an application that allows you to insert a list of individual elements (for this example, fruit), and it offers you comparisons between the two. You select your favorite from the two, and then this process repeats, until in the end you have a list ordered by the preference of these objects (in this example, a list of your favorite fruits, in order).

The problem is that traditional sorting strategies, no matter how fast, will inevitably include more operations than is possible for a person at any reasonable time (even with a list of 50, since my current test list).

Since, obviously, there is no guaranteed sorting algorithm with a sufficiently low degree of complexity, I assume that some assumptions should be made. Is there a way to skip large chunks of sorting? I looked at how to assign values ​​to elements based on the number of comparisons they “won”, and then stopped sorting after a while and suggested that these values ​​give the correct order, similar to the style that you can allow Swiss chess if you cannot go through enough rounds to determine the winner usually. I do not know how plausible it is.

An example explaining what I mean: let's say you have a list

Apple Orange Kiwi Banana Melon 

It will offer you comparisons, for example

 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 preference for these fruits.

Answer 1

What are your fruit preferences? Do you have a complete ordered list of preferences in your mind, or you have fruits that you “like more than most,” “fruits that you are“ less than most, ”and everything else that you don’t have any strong feelings - or you have not even tried.

The problem with how you formulated your problem is that you assumed that a person’s preferences are a general order that is naturally encoded as a list. Indeed, human preferences are often a partial order that is naturally encoded as a directed acyclic graph .

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

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

A good way to get a partial order based on user input is to simulate radix sorting . To get started, ask the user to choose for each fruit whether they like it, dislike it, feel neutral or don't know. I would answer like this:

  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, although I answered only as many questions as there are:

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

Then determine what answer received the majority of control signs. In this case, I seem to have 3 fruits that I like, 1 I don’t like, and I feel neutral (unless peanut butter is used), and 1 I have never tried (therefore, I have no preferences for others fruit).

So, a natural place to further study my preferences would be within the fruits that I like. The problem is recursive: now you want to determine my preferences for a set of fruits {Orange, Kiwi, Banana} . You can ask me which of these fruits is my favorite, and I would click Orange and Kiwi . This tells you the following:

 Banana < Orange Banana < Kiwi 

In combination 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 mean Apple < Kiwi ; Apple < Banana and Banana < Orange mean Apple < Orange . Therefore, we can eliminate redundant information to obtain the following:

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

Answer 2

You can allow the user not only to indicate whether an element is more preferable than another, but also a rating from 1 to 10, for example, how much he prefers one from another. Thus, you have additional information and you can easily create a rating.

In an optimal approach, when the user can talk less or more, you need to perform a 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 is a total of O(n * log (n/2)) . In the case of 50 elements, which will require more than 200 steps.

Answer 3

Use the sort insert . Instead of asking the user to compare two items at once, ask them to choose their favorite from the rest of the list. Place this item at the end of the sorted list, remove it from the remaining items and repeat until the remaining items are exhausted.