quickSort javaScript throwing Maximum call stack size exceeded

Question

why is this function throwing error

I am trying to sort array using quickSort with a recursion approach here I am using the last element in the array as a pivot

let array = [1,0,123,1,3,12,2,45,6]
function quickSort(array, leastIndex, highIndex) {
    if (leastIndex >= highIndex) return;

    const pivot = array[highIndex];
    let leftPointer = leastIndex;
    let rightPointer = highIndex;

    while (leftPointer < rightPointer) {
        while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
            leftPointer++;
        }
        while (array[rightPointer] >= pivot && rightPointer > leftPointer) {
            rightPointer--;
        }
        swap(array, leftPointer, rightPointer)
    }
    swap(array, leftPointer, highIndex);
    quickSort(array, leastIndex, leftPointer);
    quickSort(array, leftPointer + 1, highIndex);
}

function swap(array, a, b) {
    let temp = array[a]
    array[a] = array[b]
    array[b] = temp
}
quickSort(array,0,array.length-1)
console.log(array);

ERROR

Uncaught RangeError: Maximum call stack size exceeded
    at swap (<anonymous>:23:14)
    at quickSort (<anonymous>:16:9)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)
    at quickSort (<anonymous>:19:5)

Please add the error to the question so other members can help you. — Ethanolle
– Ethanolle, Commented Aug 5, 2022 at 14:25
You want the solution with the proper answer on how to do it or us to fix this one? — Ethanolle
– Ethanolle, Commented Aug 5, 2022 at 14:32
In that way you have a Stack Overflow ;p which means that your stopping point never happens and it keeps running. — Ethanolle
– Ethanolle, Commented Aug 5, 2022 at 14:33

trincot · Accepted Answer · 2022-08-05 14:57:06Z

1

The problem is that when the pivot is also the greatest value, that the first recursive call will be made with exactly the same range again, and so the partition to sort isn't becoming smaller...

Since your version of Quicksort ensures that you have the index of the pivot value (after the final swap), you can exclude that value from further recursive calls. So change:

quickSort(array, leastIndex, leftPointer);

to:

quickSort(array, leastIndex, leftPointer - 1);

answered Aug 5, 2022 at 14:57

trincot

357k38 gold badges282 silver badges338 bronze badges

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

Comments

zer0321 · Accepted Answer · 2022-08-05 14:57:07Z

0

The problem is in this line

quickSort(array, leastIndex, leftPointer);

It should be

quickSort(array, leastIndex, leftPointer - 1);

answered Aug 5, 2022 at 14:57

zer0321

1414 bronze badges

Collectives™ on Stack Overflow

quickSort javaScript throwing Maximum call stack size exceeded

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related