using for loop in quick sort in Js

user_14227985 0
Viewed 256

i am writing quick sort algorthm, and when i testing my code, the result makes me confused.

RangeError: Maximum call stack size exceeded at Array.push ()

let arr = [0,-1,1,0,1,-1,100,23,17,56,39,47,23,-34,-56];

export default function quickSort(array){
    let len = array.length;
    if(len <= 1) return array;

    let piviot = array.pop();

    let left = [], right = [];
    for (let i = 0; i < len; i++) {
        if(array[i] < piviot){
            left.push(array[i]);
        }
        else{
            right.push(array[i])
        }
    }
    return quickSort(left).concat(piviot,quickSort(right));
}

when i change for loop to forEach, problem is disappeared, but i don't know why.


export default function quickSort(array){
    let len = array.length;
    if(len <= 1) return array;

    let piviot = array.pop();

    let left = [], right = [];
    array.forEach(item => {
        if(item < piviot){
            left.push(item)
        }
        else{
            right.push(item);
        }
    });
    return quickSort(left).concat(piviot,quickSort(right));
}

Thanks.

quicksort javascript
2 Answers

This will work as piviot = array.pop(); changes array size which causes the issue

export default function quickSort(array){
    let len = array.length;
    if(len <= 1) return array;

    let piviot = array.pop();
    len = array.length;
    let left = [], right = [];
    for (let i = 0; i < len; i++) {
        if(array[i] < piviot){
            left.push(array[i]);
        }
        else{
            right.push(array[i])
        }
    }
    return quickSort(left).concat(piviot,quickSort(right));
}
user_54602610

I won't write the quicksort algorithm for you, but I will explain the behavior:

  1. Why the first piece of code overflows stack

This is very common in recursive functions that never end. You are never reaching the magic

if(len <= 1) return array;

All your function calls end up on the call stack. There is a limit depending on the browser on how many can be called on the stack at the same time. Thus when you reach that limit with recursion (and not only) you overflow the stack.

  1. Why for each works

It doesn't, it just won't overflow your stack. Why? Foreach is a callback. It won't run first and then go to the next line.

Using foreach, you are effectively calling the next recursion with empty arrays and they return automatically.

user_16436760
Related