Javascript quicksort algorithm implementation

Question

So I'm very new to javascript (came from c) and just started to learn the syntax, practicing with some exercises. I implemented a quicksort algorithm:

function sort(a)
{
    var _sort = function(l, r)
    {
        if (l >= r - 1)
            return;
        var p = r - 1;
        var y = l;
        var tmp;
        for (var i = l; i < r - 1; i++)
            if (a[i] < a[p])
            {
                tmp = a[i];
                a[i] = a[y];
                a[y] = tmp;
                y++;
            }
        tmp = a[y];
        a[y] = a[r - 1];
        a[r - 1] = tmp;
        _sort(l, y);
        _sort(y + 1, r);
    }

    _sort(0, a.length);
}

It works fine for small arrays, however for arrays beyond 5000 elements I get stack size limit exceeded. I tried to increase it, but that didn't work. I suspect there's something wrong with the way I implemented the algorithm, can it be?

My question is, how should I implement the algorithm, or bypass the stack size limitation (I think 5000 elements arrays are small), in order to make it work? I would be also glad with any style suggestions.

Could you please provide an example by using http://jsfiddle.net/ ? — Vadim Ivanov, Jul 21 '13 at 00:33
You do know that javascript alread has an Array.sort method, and in at least some browsers that will use the quicksort algorithm for certain arrays, so you're really reinventing the wheel here ? — adeneo, Jul 21 '13 at 00:33
@adeneo, I am aware of that. Whenever I learn some new language syntax, I do exercises like this. — kaspersky, Jul 21 '13 at 00:37
It looks like there's nothing wrong with your function, you could use a stack data structure to avoid the stackoverflow which as you know can happen with deep recursion — aaronman, Jul 21 '13 at 00:37
@adeneo I've considered this question as matter of curiosity. The same you can say about most of the language, that they have implementation of Array.sort method. Just for curiosity why not to implement it during the study language =) — Vadim Ivanov, Jul 21 '13 at 00:38
@VadimIvanov, http://jsfiddle.net/ebgba/ I tested the function on that framework, however it shows nothing when n goes ~5000. — kaspersky, Jul 21 '13 at 00:40
One style suggestion: instead of `var ... = function (...) { ... }`, it's usually better to write `function ...(...) { ... }`. — ruakh, Jul 21 '13 at 00:51

sabof · Accepted Answer · 2013-07-21T00:52:00.123

4

You can simulate the stack with an array, which can be longer. I did very limited testing with this, but it seemed to work.

function sort(a) {
  var stack = [[0, a.length]];
  while (1) {
    var stackLength = stack.length;
    if (! stackLength) {
      break;
    }
    var l = stack[stackLength - 1][0], 
        r = stack[stackLength - 1][1];
    if (l >= r - 1) {
      stack.pop();
      continue;
    }
    var p = r - 1;
    var y = l;
    var tmp;
    for (var i = l; i < r - 1; i++)
      if (a[i] < a[p])
    {
      tmp = a[i];
      a[i] = a[y];
      a[y] = tmp;
      y++;
    }
    tmp = a[y];
    a[y] = a[r - 1];
    a[r - 1] = tmp;
    stack.pop();
    stack.push([y + 1, r]);
    stack.push([l, y]);
  }
  return a;
}

edited Jul 21 '13 at 00:52

answered Jul 21 '13 at 00:40

sabof

8,062
4
28
52

Indeed, it seems to work. Clever hack :) So, does that mean I should be very careful when using recursive functions in javascript? – kaspersky Jul 21 '13 at 00:43
The available stack is more than enough for most tasks. http://stackoverflow.com/questions/7826992/browser-javascript-stack-size-limit If you need to do heavyweight number crunching, JavaScript is the wrong language anyway. – sabof Jul 21 '13 at 00:46
+1, but a few comments: (1) I think you should write `while(stack.length)` or `while(stack.length > 0)`. (2) I don't think `stack` is a great name; the fact that you're using the array as a stack, and that it corresponds to the recursive call-stack, is not essential. (Note that the algorithm works just as well if you select a random element from `stack`, rather than necessarily the last one.) (3) I think you should move `stack.pop()` closer to the top of the loop, so there's less fragility/risk of an infinite loop. *[continued]* – ruakh Jul 21 '13 at 00:46
(4) Instead of checking if `l >= r - 1` and `continue`-ing, I think it would make more sense to perform that comparison before `push`-ing. (That way you can use strictly structured constructs.) (5) I think `l` is a bad name, because it's easily confused with `1`. – ruakh Jul 21 '13 at 00:47
@gg.kaspersky: In JS there is no tail call optimization. You could look into memoization for caching, Underscore has an implementation of `memoize`, check http://underscorejs.org/#memoize – elclanrs Jul 21 '13 at 00:48
@elclanrs: Tail call optimization would not help here, because one of the recursive calls is not a tail call. – ruakh Jul 21 '13 at 00:49
(Oh, I forgot to say what I'd suggest instead of `stack`. I think something like `rangesToSort` would be better.) – ruakh Jul 21 '13 at 00:49
@ruakh acessing .lenght is slow, so I wrote it a little differently. I only translated gg.kaspersky's algorithm, and I'm rather oblivious as to how it actually works, and what's best. – sabof Jul 21 '13 at 00:57
@sabof: Re: "acessing .lenght is slow": That's not true. Or at least -- it's no slower than anything else in JavaScript. (Accessing `a[i]`, for example, is just as bad.) – ruakh Jul 21 '13 at 01:00
@ruakh lenght is not a property, but a method with a property's interface, so it's likely to peform differently. I'd think it should be easy for the VM to optimize multiple consecutive .lenght calls, but I don't know whether it does. – sabof Jul 21 '13 at 01:05

score 4 · Answer 2 · answered Jul 21 '13 at 00:52

As you know, quicksort has pathologically bad performance for input that is already sorted or reverse sorted. In these cases you end up using O(n) stack space, which can lead to a stack overflow error.

To avoid these problem cases you could choose the pivot element "y" as the median of three (first, middle and last), though apparently there are sequences that trigger pathological performance even then. To completely rid yourself of this problem you could implement merge sort or heap sort instead. Or use an array as a stack instead of using recursion.

Very good observation! Indeed, the problem was that it happened so that I used the worst case (reversely sorted arrays), so there were tons of recursive calls :) — kaspersky, Jul 21 '13 at 00:55

Javascript quicksort algorithm implementation

2 Answers2