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\$
    – wOxxOm
    Jun 3, 2017 at 8:09
  • \$\begingroup\$ ...(4x with slice() so once its time is subtracted the difference should be much bigger). \$\endgroup\$
    – wOxxOm
    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\$
    – Tobi
    Jun 3, 2017 at 10:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.