Question

165

Infinite recursion in JavaScript quicksort?

rated 0 times [ 171] [ 6] / answers: 1 / hits: 40592 / 12 Years ago, thu, february 7, 2013, 12:00:00

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

    }

}

Answers

Only authorized users can answer the question. Please sign in first, or register a free account.

manuel

Add To Favorites

Follow

Total Points: 747

Total Questions: 96

Total Answers: 95

Location: Argentina

Member since Thu, Mar 18, 2021

3 Years ago

answered 12 Years ago breap · Accepted Answer

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.