Sorting a set of objects by a user's preference

Question

Given a set of n objects in no specific order (n = 5 in this example):

{
    apple,
    orange,
    banana,
    cherry,
    cabbage
}

I'm trying to give a user several questions with three options, like so:

banana      vs.      cabbage
      (no preference)

after every question, it would make a new question with different options (no preference stays the same), efficiently collecting data on the user's preferences.

It would, after several (6 or 7 in this case) questions, give an ordered list (array) of the highest ranked objects in order:

{
    cherry,
    cabbage,
    orange,
    apple,
    banana
}

However, I don't know how such an algorithm would work or when it would know to stop. I'm sorry if this is a bad question, but I'm pretty new to algorithm design.

And I suppose it doesn't really matter, but I'm using JavaScript.

---

Okay, I'm revisiting this four months later, because I thought of a new method to do the sorting.

Perhaps, it would be more efficient to have a list of inferiors for each object, so that anything which is inferior to one object would be inferior for its superiors. I'm explaining this awfully, so here's a visual:

cherry > cabbage
cabbage > banana
cabbage > apple
apple > orange

thus, cherry > cabbage & banana & apple & orange

With the old method, with score:

apple vs. orange
apple vs. banana (e.g. apple wins)
apple vs. cherry (e.g. cherry wins)
apple vs. cabbage
orange vs. banana
orange vs. cherry
orange vs. cabbage
banana vs. cherry
banana vs. cabbage
cherry vs. cabbage

10 questions

The new method would make cherry vs. banana redundant because we already know that apple > banana and cherry > apple. I really only need to figure out how to code it.

The only problem arises with human circular logic (i.e. a > b > c > a), where this is a possibility, but thankfully this won't be a problem with my particular set.

Answer 1

I looked into this some time ago as part of my answer to a related question (Collaborative sorting algorithm based on 1 vs 1 choice) and found that creating an ordered list based on "do you prefer A or B?" style questions, using as few questions as possible, and while avoiding cycles (as in: A>B, B>C, C>A), is best done using binary insertion sort, or a variation thereof.

What this means in practise, is that you introduce the elements into the ordered list one by one, find their place in the list, insert them, and then move on to the next element.
To reduce the number of comparisons to the strictest minimum, you use binary insertion; this means that every new element is first compared to the element in the middle of the ordered list; this tells you whether the new element goes in the upper or lower half; then you compare it to the element in the middle of that half, and so on, until its place is found.

As an example, consider a list of 10 elements that need to be sorted. If you compared every element with every other element, you'd have to ask 45 questions. With binary insertion, this is reduced to 19 ~ 25 questions, with an average of 22.2 questions.

The exact number of questions depends on the input: to insert 1 into the list [2,4,6,8], you'd compare it with 4, then with 2, and you'd know its location with two comparisons; to insert 7 into the list [2,4,6,8], you'd compare it with 4, then with 6, then with 8, and only know its location after three comparisons. In general, inserting the n-th elements takes either log₂(n) or log₂(n)+1 comparisons (always log₂(n) if n is a power of 2). The overall number of comparisons < n.log_e(n).

If you accept "no preference" answers, the number of questions can be lower, down to n-1 if most of the answers are "no preference".

Below is a Javascript code snippet I wrote for the related question. It asks "A or B?" questions, takes "A", "B" or "no preference" as answers, and creates an ordered list. A random generator acts as the person giving the answers.

The algorithm could be adapted to sort the array in-place. You'd start by considering the first element as the sorted array, and the second element as the element to be inserted, and swap them if necessary; then you'd consider the first two elements as the sorted list, and the third element as the element to be inserted, and so on. For variations of binary insertion sort, and strategies to reduce the number of swaps, see e.g. this Wikipedia article.

function PrefList(n) {
    this.size = n;
    this.items = [{item: 0, equals: []}];
    this.current = {item: 1, try: 0, min: 0, max: 1};

    this.addAnswer = function(x, y, pref) {
        if (pref == 0) {
            this.items[this.current.try].equals.push(this.current.item);
            this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
        } else {
            if (pref == -1) this.current.max = this.current.try
            else this.current.min = this.current.try + 1;
            if (this.current.min == this.current.max) {
                this.items.splice(this.current.min, 0, {item: this.current.item, equals: []});
                this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
            }
        }
    }

    this.getQuestion = function() {
        if (this.current.item >= this.size) return null;
        this.current.try = Math.floor((this.current.min + this.current.max) / 2);
        return({a: this.current.item, b: this.items[this.current.try].item});
    }

    this.getOrder = function() {
        var index = [];
        for (var i in this.items) {
            var equal = [this.items[i].item];
            for (var j in this.items[i].equals) {
                equal.push(this.items[i].equals[j]);
            }
            index.push(equal);
        }
        return(index);
    }
}

// THIS FUNCTION ACTS AS THE PERSON ANSWERING THE QUESTIONS
function preference(a, b) {
    if (Math.random() > 0.6) return -1; else if (Math.random() > 0.333) return  1; else return 0;
}

// CREATE TABLE AND ASK QUESTIONS UNTIL TABLE IS COMPLETE
var fruit = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry", "starfruit", "strawberry"];
var t = new PrefList(10), c = 0, q;
while (q = t.getQuestion()) {
    document.write(++c + ". " + fruit[q.a] + " or " + fruit[q.b] + "?<BR>");
    var answer = preference(fruit[q.a], fruit[q.b]);
    document.write("&nbsp;&rarr; " + [fruit[q.a], "no preference", fruit[q.b]][answer + 1] + "<BR>");
    t.addAnswer(q.a, q.b, answer);
}

// PERFORM SORT BASED ON TABLE AND DISPLAY RESULT
var index = t.getOrder();
document.write("LIST IN ORDER:<BR>");
for (var i = 0, pos = 1; i < index.length; i++) {
    var pre = pos + ". ";
    for (var j = 0; j < index[i].length; j++) {
        document.write(pre + fruit[index[i][j]] + "<BR>");
        pre = "&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    pos += index[i].length;
}

Answer 2

You can use sort:

var sorted = "cherry,cabbage,orange,apple,banana".split(",").sort(function(a,b) {
  return prompt([
    "If you prefer " + a + ", enter -1",
    "If you prefer " + b + ", enter 1",
    "If you don't mind , enter 0"
  ].join("\n"));
});