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.

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
– adeneo, Commented Jul 21, 2013 at 0:33
@adeneo, I am aware of that. Whenever I learn some new language syntax, I do exercises like this. — kaspersky
– kaspersky, Commented Jul 21, 2013 at 0: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
– aaronman, Commented Jul 21, 2013 at 0: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
– Vadim Ivanov, Commented Jul 21, 2013 at 0:38

sabof · Accepted Answer · 2013-07-21 00:52:00Z

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, 2013 at 0:52

answered Jul 21, 2013 at 0:40

sabof

8,2024 gold badges32 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

kaspersky Over a year ago

Indeed, it seems to work. Clever hack :) So, does that mean I should be very careful when using recursive functions in javascript?

sabof Over a year ago

The available stack is more than enough for most tasks. stackoverflow.com/questions/7826992/… If you need to do heavyweight number crunching, JavaScript is the wrong language anyway.

ruakh Over a year ago

+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 Over a year ago

(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.

elclanrs Over a year ago

@gg.kaspersky: In JS there is no tail call optimization. You could look into memoization for caching, Underscore has an implementation of memoize, check underscorejs.org/#memoize

|

Joni · Accepted Answer · 2013-07-21 00:52:11Z

4

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.

answered Jul 21, 2013 at 0:52

Joni

112k14 gold badges151 silver badges201 bronze badges

1 Comment

kaspersky Over a year ago

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 :)

Collectives™ on Stack Overflow

Javascript quicksort algorithm implementation

2 Answers 2

10 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

10 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related