Insertion sort slower than bubble sort

up vote
3
down vote

favorite

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.

edited 10 mins ago

Jamal♦

30.2k11115226

asked Jun 3 '17 at 0:37

Tobi

1716

1

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.
– wOxxOm
Jun 3 '17 at 8:09

...(4x with slice() so once its time is subtracted the difference should be much bigger).
– wOxxOm
Jun 3 '17 at 10:11

1

I didn't notice that I hadn't re-assign/copy the array! Obvious hole in my testing
– Tobi
Jun 3 '17 at 10:14

add a comment |

up vote
3
down vote

favorite

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.

edited 10 mins ago

Jamal♦

30.2k11115226

asked Jun 3 '17 at 0:37

Tobi

1716

1

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.
– wOxxOm
Jun 3 '17 at 8:09

...(4x with slice() so once its time is subtracted the difference should be much bigger).
– wOxxOm
Jun 3 '17 at 10:11

1

I didn't notice that I hadn't re-assign/copy the array! Obvious hole in my testing
– Tobi
Jun 3 '17 at 10:14

add a comment |

up vote
3
down vote

favorite

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.

edited 10 mins ago

Jamal♦

30.2k11115226

asked Jun 3 '17 at 0:37

Tobi

1716

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.

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);

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);

javascript performance sorting insertion-sort

edited 10 mins ago

Jamal♦

30.2k11115226

asked Jun 3 '17 at 0:37

Tobi

1716

edited 10 mins ago

Jamal♦

30.2k11115226

asked Jun 3 '17 at 0:37

Tobi

1716

edited 10 mins ago

Jamal♦

30.2k11115226

edited 10 mins ago

Jamal♦

30.2k11115226

edited 10 mins ago

Jamal♦

30.2k11115226

asked Jun 3 '17 at 0:37

Tobi

1716

asked Jun 3 '17 at 0:37

Tobi

1716

asked Jun 3 '17 at 0:37

Tobi

1716

1

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.
– wOxxOm
Jun 3 '17 at 8:09

...(4x with slice() so once its time is subtracted the difference should be much bigger).
– wOxxOm
Jun 3 '17 at 10:11

1

I didn't notice that I hadn't re-assign/copy the array! Obvious hole in my testing
– Tobi
Jun 3 '17 at 10:14

add a comment |

1

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.
– wOxxOm
Jun 3 '17 at 8:09

...(4x with slice() so once its time is subtracted the difference should be much bigger).
– wOxxOm
Jun 3 '17 at 10:11

1

I didn't notice that I hadn't re-assign/copy the array! Obvious hole in my testing
– Tobi
Jun 3 '17 at 10:14

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.
– wOxxOm
Jun 3 '17 at 8:09

...(4x with slice() so once its time is subtracted the difference should be much bigger).
– wOxxOm
Jun 3 '17 at 10:11

I didn't notice that I hadn't re-assign/copy the array! Obvious hole in my testing
– Tobi
Jun 3 '17 at 10:14

add a comment |

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f164819%2finsertion-sort-slower-than-bubble-sort%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

active

oldest

votes

draft saved

draft discarded

Thanks for contributing an answer to Code Review Stack Exchange!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Tukukkk