using for loop in quick sort in Js

Question

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.

implementing fundamental algorithms on a highly referenced language like javascript will prove problematic ... thats the short answer — GetSet
– GetSet, Commented Sep 6, 2020 at 6:32

Ravi · Accepted Answer · 2020-09-06 06:32:11Z

2

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

answered Sep 6, 2020 at 6:32

Ravi

2,2912 gold badges18 silver badges30 bronze badges

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

Comments

Athanasios Kataras · Accepted Answer · 2020-09-06 06:38:07Z

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

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.

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.

Collectives™ on Stack Overflow

using for loop in quick sort in Js

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