I am trying to come up with the best sorting algorithm when the actual comparison count is not a concern but how to compare is not known by the computer, thus needing user input.
For example let's say there is an array of foods, [apple, banana, orange, pear] and we want to sort it from the best to the worst. To know if apple or banana is better the user needs to answer it. However, if we know apple is better than banana and banana is better than orange (=user already provided input for those comparisons), then no input is necessary to compare apple and orange.
What kind of sorting algorithm can be used to minimize the times we ask the user for an input?
Edits for clarification:
(I read all the comments and realized I hadn't done a good job of explaining my question.)
Let's continue with the example above:
- There is a list of size n containing fruits.
- We are trying to sort the list from the user's most favorite fruit to the least.
- There are no duplicate fruits and the preference is transitive (A>B & B>C implies A>C)
- The user has a strong preference. (Either A>B or B>A)
- At first, we don't know anything about the user's preference and we can only learn about it by showing them 2 fruits and asking which one they prefer. We don't care about how many comparisons the computer does (it can even do selection sort) but we are trying to minimize the number of questions we ask the user.
The worst case scenario is asking (n!/(2(n-2)!)) questions as it is the number of pairs and the best case is (getting lucky) and asking (n-1) questions.
What kind of algorithm can be used to minimize the number of questions asked to the user?
n log n. The real question is "What is the minimal number of queries to the user?".ask_humanand thus reduce number of queries, of course this function will be called as many times as compare, but it will ask user less times it is actually called