2
\$\begingroup\$ 

Array.prototype.insertionSort = function(){
    for (var i=1, s,temp; i<this.length; i++){
         temp = this[s=i];
         while (s&&temp<this[s-1]) this[s] = this[--s];
         this[s] = temp;
    }
    return this 
}

Array.prototype.bubbleSort = function(){  
    var swapped = true;
    while (swapped) {
        swapped = false;
        for (var i = 0; i<this.length-1; i++) if (this[i]>this[i+1]) {
            var temp = this[i];
            this[i] = this[i+1];
            this[i+1] = temp;
            swapped = true;
        }
    }
    return this;
}

var array = [1,4,4,5,6,7,5,3,5,67,7,4,3,5,76,234,24,235,24,4,234,234,234,325,32,6246,8,89,689,7687,56,54,643,32,213,2134,235,346,45756,857,987,0790,89,57,5,32,423,54,6,765,65,745,4,34,543,43,3,3,3,34,3,63,63,35,7,537,35,75,754,7,23,234,43,6,247,35,54,745,767,5,3,2,2,6,7,32,3,56,346,4,32,32,3,4,45,5,34,45,43,43],

    iter = 10000000;

console.time("bubble x"+iter);
for (var i = iter; i--;) array.bubbleSort();
console.timeEnd("bubble x"+iter);

console.time("insertion x"+iter);
for (var i = iter; i--;) array.insertionSort();
console.timeEnd("insertion x"+iter);

The insertion sort should be quicker, right? Is there something wrong with an implementation of mine?

bubble x10000000: 3131ms

insertion x10000000: 4287ms

I didn't even apply the optimisation, to the bubble sort, that decrements the loop length every iteration.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ bubble 2.7s and insertion 2.3s here so I'd say it depends on internal optimization quirks of js engine. You should have used the original array for both algos in each iteration array.slice().bubbleSort(); and array.slice().insertionSort(); in which case insertionSort is 4x faster. \$\endgroup\$ Commented Jun 3, 2017 at 8:09
  • \$\begingroup\$ ...(4x with slice() so once its time is subtracted the difference should be much bigger). \$\endgroup\$ Commented Jun 3, 2017 at 10:11
  • 1
    \$\begingroup\$ I didn't notice that I hadn't re-assign/copy the array! Obvious hole in my testing \$\endgroup\$ Commented Jun 3, 2017 at 10:14

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.