prac64's blog

By prac64, history, 5 years ago, In English

For a personal project I'm working on, I need to sort a list by asking user preferences. Naturally the list can't be too long, at most 20 values. Now since complexity is not an issue, I'm focussing on reducing the number of questions asked. My initial idea was to use library sort and overload the custom comparator which then takes user input. But it seems to me that it's asking too many questions. I've also used a memoizing table, which returns answer for (x,y) if (x,y) or (y,x) has been answered by user before, but it's still unsatisfactory.

Help me design a sort which asks for minimum comparisons. Complexity of computation is not much of an issue, go wild.

  • Vote: I like it
  • +37
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's a hard problem and the minimum number is known only for small values for N (I don't know about the strategies) — https://oeis.org/A036604. I guess you should try a few different algorithms and see which one behaves best.

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Why don't you just give the user the list of 20 items and ask them to sort the items? As a user I would strongly prefer this to being asked almost 100 different yes/no comparisons.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I developed this because I had trouble figuring out the ranking between items, and binary choices were easier to make than entire sort. But I see your point, in some applications, asking the entire ranking could be more viable. In this case, I did something like this precisely because it was difficult to make choices in sorting.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably, this problem is similar to yours. And smth alike on quora