quickSort javaScript throwing Maximum call stack size exceeded-CodePudding

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)

CodePudding user response：

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

CodePudding user response：

The problem is in this line

quickSort(array, leastIndex, leftPointer);

It should be

quickSort(array, leastIndex, leftPointer - 1);