CODEWITHSUNDEEP
javascriptarrayssortingcomputer-science
Hao Luo
Hao Luo

Reputation: 1891

Why is Selection Sort so fast in Javascript?

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

Upvotes: 1

Views: 818

Answers (1)

Bergi
Bergi

Reputation: 664548

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.

Upvotes: 2

Related Questions