Why is Selection Sort so fast in Javascript?

Question

I'm studying for a technical interview right now, and writing quick javascript implementations of different sorts. The random-array benchmark results for most of the elementary sorts makes sense but the selection sort is freakishly fast. And I don't know why.

Here is my implementation of the Selection Sort:

Array.prototype.selectionSort = function () {
  for (var target = 0; target < this.length - 1; target++) {
    var min = target;
    for (var j = target + 1; j < this.length - 1; j++) {
      if (this[min] > this[j]) {
        min = j;
      }
    }
    if (min !== target) {
      this.swap(min, target);
    }
  }
}

Here are the results of the same randomly generated array with 10000 elements:
BubbleSort => 148ms
InsertionSort => 94ms
SelectionSort => 91ms
MergeSort => 45ms

All the sorts are using the same swap method. So why is Selection Sort faster? My only guess is that Javascript is really fast at array traversal but slow at value mutation, since SelectionSort uses the least in value mutation, it's faster.

** For Reference **
Here is my Bubble Sort implementation

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

Here is the swap Implementation

Array.prototype.swap = function (index1, index2) {
  var val1 = this[index1],
      val2 = this[index2];
  this[index1] = val2;
  this[index2] = val1;
};

You could find out if your implementation is correct: check if the resulting array is sorted. — 11684
– 11684, Commented May 3, 2014 at 20:56
Why are the other sorts so slow? Surely sorting a 10,000 element array shouldn't take seconds. — AsksAnyway
– AsksAnyway, Commented May 3, 2014 at 20:59
Selection sort is 2x faster than Bubble sort, because it makes 10 000 less writes into array. Isn't it obvious? Each primitive action is going to take some time. — Ivan Kuckir
– Ivan Kuckir, Commented May 3, 2014 at 22:44
Just two comments: The swap function can be implemented with just three assignments, not four. Also, the test if (min !== target) is not a good idea: For the few cases it will save some time in the swap, all other cases will loose time in the test. — anumi
– anumi, Commented May 5, 2014 at 8:39

Bergi · Accepted Answer · 2014-05-04 13:03:31Z

First let me point out two flaws:

The code for your selection sort is faulty. The inner loop needs to be
```
for (var j = target + 1; j < this.length; j++) {
```
otherwise the last element is never selected.
Your jsperf tests sort, as you say, the "same randomly generated array" every time. That means that the successive runs in each test loop will try to sort an already sorted array, which would favour algorithms like bubblesort that have a linear best-case performance.

Luckily, your test array is so freakishly large that jsperf runs only a single iteration of its test loop at once, calling the setup code that initialises the array before every run. This would haunt you for smaller arrays, though. You need to shuffle the array inside the "timed code" itself.

Why is Selection Sort faster? My only guess is that Javascript is really fast at array traversal but slow at value mutation.

Yes. Writes are always slower than reads, and have negative effects on cached values as well.

SelectionSort uses the least in value mutation

Yes, and that is quite significant. Both selection and bubble sort do have an O(n²) runtime, which means that both execute about 100000000 loop condition checks, index increments, and comparisons of two array elements.

However, while selection sort does only O(n) swaps, bubble sort does O(n²) of them. That means not only mutating the array, but also the overhead of a method call. And that much much more often than the selection sort does it. Here are some example logs:

> swaps in .selectionSort() of 10000 element arrays
9989
9986
9992
9990
9987
9995
9989
9990
9988
9991
> swaps in .bubbleSort() of 10000 element arrays
24994720
25246566
24759007
24912175
24937357
25078458
24918266
24789670
25209063
24894328

Ooops.

Thanks for the awesome answer! I saw the error in my code last night and fixed it :)

Collectives™ on Stack Overflow

Why is Selection Sort so fast in Javascript?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related