quicksort in js

JavaScript performance comparison

Revision 8 of this test case created by imma

Info

data looked a bit suspect - making it randomised & pre-prepared the sort functions

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var arr, n;
    function randomize() { arr = []; n = 100;
      while (n--) arr.push(100*Math.random()); }
    randomize();
   
    function qs1(a) {
      if (a.length <= 1) { return a; }
      var pivot = a.pop(),
          left = [], right = [];
      a.forEach(function(v) {
        (v < pivot ? left : right).push(v); })
      return qs1(left).concat(pivot, qs1(right)); }
   
    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)); }
   
    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)); }
   
    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)); }
   
    function qs5(a) {
      if (a.length <= 1) { return a; }
      var pivot = a.pop(),
          left = [], right = [],
          n, l = a.length;
      for (n = 0; n < l; n++) {
        var v = a[n];
        (v < pivot ? left : right).push(v); }
      return qs5(left).concat(pivot, qs5(right)); }
   
    function qs6(a) {
      if (a.length <= 1) { return a; }
      var pivot = a.pop(),
          left = [], right = [],
          n, l = a.length;
      for (n = 0; n < l; n++) {
        var v = a.pop();
        (v < pivot ? left : right).push(v); }
      return qs6(left).concat(pivot, qs6(right)); }
   
    function qs(a) {
      a.sort(function(a,b) { return a-b; }); }
};

Benchmark.prototype.teardown = function() {
    /* re-randomise between tests */
    randomize();
};
</script>

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 = qs1(arr);
pending…
Efficient
var sorted = qs2(arr);
pending…
Efficient2
var sorted = qs3(arr);
pending…
qs4
var sorted = qs4(arr);
pending…
native
var sorted = qs(arr);
pending…
Fancy For
var sorted = qs5(arr);
pending…
native1
var sorted = arr.sort();
pending…
FFpop+
var sorted = qs6(arr);
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