quicksort in js

JavaScript performance comparison

Revision 5 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 = 100;
    while (n--) arr.push(100*Math.random());
   
    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 qs(a) {
      a.sort(function(a,b) { return a-b; }); }
};
</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…
More Efficient
var sorted = qs3(arr);
pending…
qs4
var sorted = qs4(arr);
pending…
native Array#sort()
var sorted = qs(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:

2 comments

imma (revision owner) commented :

umm, that's a scary result. must have broken something :-(

imma (revision owner) commented :

nope, seems fine ... confusing

Add a comment