quicksort in js

JavaScript performance comparison

Revision 3 of this test case created

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Fancy
var sorted = qs([34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44, 34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44]);

function qs(a) {

  if (a.length <= 1) {
    return a;
  }

  var pivot = a.pop(),
      left = [],
      right = [];

  a.forEach(function(v) {
    (v < pivot ? left : right).push(v);
  })

  return qs(left).concat(pivot, qs(right));

}
pending…
Efficient
var sorted = qs2([34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44, 34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44]);

function qs2(a) {

  if (a.length <= 1) {
    return a;
  }

  var left = [],
      right = [],
      i, pivot = a[0],
      l = a.length;

  for (i = 1; i < l; i++) {
    if (pivot < a[i]) {
      left[left.length] = a[i];
    } else {
      right[right.length] = a[i];
    }
  }

  return qs2(left).concat(pivot, qs2(right));

}
pending…
More Efficient
var sorted = qs3([34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44, 34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44]);

function qs3(a) {

  if (a.length <= 1) {
    return a;
  }

  var left = [],
      right = [],
      i, v, pivot = a[0],
      l = a.length;

  for (i = 1; i < l; i++) {
    v = a[i];
    if (pivot < v) {
      left[left.length] = v;
    } else {
      right[right.length] = v;
    }
  }

  return qs3(left).concat(pivot, qs3(right));

}
pending…
qs4
var sorted = qs4([34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44, 34, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 4434, 2, 45, 3, 3, 645, 6, 1, 7, 567, 44]);

function qs4(a) {

  if (a.length <= 1) {
    return a;
  }

  var left = [],
      right = [],
      i, pivot = a[0],
      l = a.length;

  for (i = 1; i < l; i++) {
    if (pivot < a[i]) {
      left[left.length] = a[i];
    } else {
      right[right.length] = a[i];
    }
  }

  return qs4(left).concat(pivot, qs4(right));

}
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment