Infinite recursion in JavaScript quicksort?

Question

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));
    }
}

You are overwriting l and r each recursive call. You should init them outside of your sort function. — marteljn
– 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
– Yujun Wu, Commented Feb 7, 2013 at 21:16
I have to ask: What's wrong with just calling originalArray.sort()? — Niet the Dark Absol
– Niet the Dark Absol, 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? — templatetypedef
– templatetypedef, Commented Feb 7, 2013 at 22:07

starball · Accepted Answer · 2022-12-22 21:35:49Z

341

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.

edited Dec 22, 2022 at 21:35

starball♦

59.7k53 gold badges317 silver badges1k bronze badges

answered Feb 7, 2013 at 21:20

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

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

8 Comments

templatetypedef Over a year ago

@Bergi- Thanks! I'm by no means a JS programmer, and I didn't know that you could do that.

Lester Peabody Over a year ago

gg Randall. Let's get some stats on API access calls against the sort tag? :)

Vicky Chijwani Over a year ago

I bet @templatetypedef gained a lot of reputation today because of that stacksort implementation :)

vlasits Over a year ago

Up voted solely because this worked in the hilarious stacksort project (gkoberger.github.com/stacksort)

Cyril N. Over a year ago

And @templatetypedef is wondering why is answer is having so much popularity now ... thanks to stacksort ;)

|

Clemens Klein-Robbenhaar · Accepted Answer · 2013-02-07 21:25:24Z

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. ;)

answered Feb 7, 2013 at 21:25

Clemens Klein-Robbenhaar

3,5371 gold badge21 silver badges27 bronze badges

Comments

Peter Mortensen · Accepted Answer · 2013-08-02 18:47:31Z

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.

edited Aug 2, 2013 at 18:47

Peter Mortensen

31.4k22 gold badges110 silver badges134 bronze badges

answered Feb 7, 2013 at 21:23

user1115652

2 Comments

templatetypedef Over a year ago

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.

user1115652 Over a year ago

your question doesn't mention anything about infinite recursion, rather about the variables not changing...

Collectives™ on Stack Overflow

Infinite recursion in JavaScript quicksort?

3 Answers 3

8 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related