current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

With the help of some nice folks at Stack Overflow, I wrote an algorithm that will give a user three buttons: option a neither option b Clicking on a button will add one to the score of a object, and it will systematically go through each match-up to get an equal amount of questions for each character.

Here's the meat of the function:

var pos1 = 0; //position in the array
var pos2 = 1; //ditto

var array = [ //array used
    {name: "apple", score: 0},
    {name: "pear", score: 0},
    {name: "cherry", score: 0},
    {name: "banana", score: 0},
    {name: "orange", score: 0},
    {name: "watermelon", score: 0},
    {name: "bread" score: 0},
    {name: "a duck" score: 0}
]

var option1 = array[0]; //keeps track of which option is shown in the button
var option2 = array[1]; //ditto

function select(slot) { //called when user presses button
    if (slot == 1) { //left button
        array[pos1].score++;
    } else if (slot == 2) { //right button
        array[pos2].score++;
    } //for neither, it does select(0)

    if (pos2 < array.length - 1) {
        pos2++;
        option2 = array[pos2];
    } else if (pos1 < array.length - 2) {
        pos1++;
        pos2 = 1 + pos1;
        option1 = array[pos1]
        option2 = array[pos2]
    } else {
        output(); //sorts and displays
        return;
    }
}

It works pretty well for smaller numbers of objects, but it gets totally absurd at higher numbers. For example, in practice, one of my sets has around 50 objects, resulting in ~1500 questions, which takes hours!

As a side note, I found this website. Ignoring the content, it's able to sort a similar number (55) of objects with only 170 questions. It's also somehow able to generate a percentage of completion, but that's just a bonus.

Conveniently, the author has the code embedded directly in the HTML, so the JavaScript is easy to view. However, I can't figure out how it works, but it's the type of efficiency I'm looking for.

share|improve this question

2 Answers 2

up vote 2 down vote

You'll have to excuse my javascript, which is kind of lacking, but you can use any comparison based algorithm to make the sorting happen in \$O(n \log n)\$ comparisons, where a comparison is one of your user powered tests. I think merge sort is guaranteed to need exactly \$n \log n\$, and is relatively simple to implement, so you could implement a bottom-up mergesort by doing something along the lines of:

var array = ["apple", "pear", "cherry",  "banana", "orange", "watermelon",
             "bread", "a duck"];
var temp = [];

var merge_len = 1
var merge_lo = 0;
var merge_mid = 1;
var merge_hi = 2;
var merge_ptr_1 = 0;
var merge_ptr_2 = 1;

function mergesort_step(slot) {
    if (slot == 2) { // right button pressed
        temp.push(array[merge_ptr_2]);
        merge_ptr_2++;
    }
    else {
        temp.push(array[merge_ptr_1]);
        merge_ptr_1++;
    }

    if (merge_ptr_1 == merge_mid || merge_ptr_2 == merge_end) {
        // Copy any remaining items in 1st merged subarray to temp
        for (i = merge_ptr_1; i < merge_mid; merge_ptr_1++) {
            temp.push(array[merge_ptr_1]);
        }
        // Copy any remaining items in 2nd merged subarray to temp
        for (i = merge_ptr_2; i < merge_hi; merge_ptr_2++) {
            temp.push(array[merge_ptr_2]);
        }
        // Overwrite the two subarrays with the sorted temp
        for (i = 0; i < merge_hi - merge_lo; i++) {
            array[i + merge_lo] = temp[i];
        }
        temp = []
        // Set up the next two subarrays to merge
        if (merge_hi + merge_len >= array.length) {
            merge_lo = 0;
            merge_len *= 2;
            if (merge_len >= array.length) {
                // We are finished!
                output();
                return
            }
        }
        else {
            merge_lo = merge_hi;
        }
        merge_mid = merge_lo + merge_len;
        merge_hi = merge_mid + merge_len;
        if (merge_hi > array.length) {
            merge_hi = array.length();
        }
        merge_ptr_1 = merge_lo;
        merge_ptr_2 = merge_mid;
    }
}

Here merge_ptr_1 and merge_ptr_2 have taken the place of your pos1 and pos2, and I have skipped your option1 and option2 entirely to not bloat the code up any more.

share|improve this answer
    
The code doesn't account for the user clicking on the "neither" button, and goes straight to the left button instead, right? –  Poyo Jul 27 at 17:49
    
Yes, I'm equating your three options to larger than, equal to, greater than. As far as sorting goes, it is sufficient to know if one is greater than the other or not, no need to explicitly check for equality. –  Jaime Jul 27 at 18:06
    
I typed this into my JavaScript console, but the function times out when I mergesort_step(1). Do you have any idea why this could be? (Also, sorry if I'm being naggy) –  Poyo Jul 27 at 18:37
up vote 1 down vote

I've cleaned up a little bit your code and also I've done a bech test (using a loop to add more objects into the array).

  • Added ";" in line ending for every line
  • Chainned variables (good practise)
  • Added the test bench calculating the time

The results: the code runs entirely in just 6 seconds ! So, I think your time issue is elsewhere. Let me know

You can see it here: http://jsfiddle.net/jgauna/0nq7ajzf/2/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.