31

Here is the quicksort code I wrote. The function doesn't work because it can't reach the base case. If I log the pivot, r and l to the console, they remain the same no matter how many times the sort function is called. So I wonder if the argument l, r are not really passed into the function as data. Why did it happen?

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}
4
  • 3
    You are overwriting l and r each recursive call. You should init them outside of your sort function.
    – marteljn
    Commented Feb 7, 2013 at 21:14
  • @marteljn Yes. But if i put console.log(l) before the return, it prints the same arrays.So I am confused
    – Yujun Wu
    Commented Feb 7, 2013 at 21:16
  • 3
    I have to ask: What's wrong with just calling originalArray.sort()? Commented Feb 7, 2013 at 21:20
  • @marteljn- Are you sure about that? Won't each call get its own stack frame and its own local copy of l and r? Commented Feb 7, 2013 at 22:07

3 Answers 3

339

I think that the issue here is that your partitioning step does not necessarily shrink the input array. For example, let's trace what happens if you try sorting [1, 2]. In this case, your pivot element will be the element 2. Since 1 > 2 is false, 1 is added to the list l. Since 2 > 2 is false, 2 is added to the list l. As a result, your recursive call on the list l will have exactly the same arguments as your original call, causing infinite recursion.

To fix this, try splitting the input into three lists - one of smaller values, one of equal values, and one of greater values. This code is shown here:

function sort(data){
  if (data.length < 2){
    return data;
  } else {
    var l = [];
    var r = [];
    var e = [];
    var i = 0;
    var pivot = (data.length / 2) | 0;

    for(i = 0; i < data.length; i++) {
      if (data[i] > data[pivot]) {
        r.push(data[i]);
      } else if (data[i] < data[pivot]) {
        l.push(data[i]);
      } else {
        e.push(data[i]);
      }
    }  
    return sort(l).concat(e, sort(r)); 
  }
}

This new version explicitly groups the equal elements into their own list, so they aren't recursively sorted by either of the recursive calls. It also gracefully handles duplicate elements.

8
  • 1
    @Bergi- Thanks! I'm by no means a JS programmer, and I didn't know that you could do that. Commented Feb 7, 2013 at 21:26
  • 8
    gg Randall. Let's get some stats on API access calls against the sort tag? :) Commented Mar 18, 2013 at 19:05
  • 108
    I bet @templatetypedef gained a lot of reputation today because of that stacksort implementation :) Commented Mar 18, 2013 at 19:56
  • 134
    Up voted solely because this worked in the hilarious stacksort project (gkoberger.github.com/stacksort)
    – vlasits
    Commented Mar 18, 2013 at 20:22
  • 10
    And @templatetypedef is wondering why is answer is having so much popularity now ... thanks to stacksort ;)
    – Cyril N.
    Commented Mar 19, 2013 at 8:56
1

If you pick the largest value of the array as the pivot element, then all values of data will end up in the array l and none in r. Thus will make the recursion never stop (and keep l, r and pivot at the same values). Unless this is a brain excercise, using data.sort() should do a better job. ;)

0

JavaScript passes objects by reference (arrays are objects too). If you want to pass them by value, you need to use the splice function as explained here.

Note that this will create a lot of copies of your data. You probably want to use the native sort() function.

2
  • 1
    I don't think that's the problem here. The infinite recursion is not because of pass-by-reference, but due to the fact that the original code does not correctly handle one of the cases it needs to handle. Commented Feb 7, 2013 at 21:24
  • your question doesn't mention anything about infinite recursion, rather about the variables not changing...
    – user1115652
    Commented Feb 7, 2013 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.