Implement the Quicksort Algorithm - Implement the Quicksort Algorithm

Curriculum Help
1

Tell us what’s happening:

So for the quicksort algorithm, I had to look up online, how I could fix my solution, since my version with filtering the array causes too much recursion.
The thing is, the path with the for loop also looks like it should cause stack overflow, but for some reason it doesn’t and I don’t understand why it doesn’t.

Your code so far

function quicksort(arr) {
  if (arr.length <= 1) return arr;

  let pivot = arr[arr.length - 1];

  // too much recursion:
  // const left = arr.filter((curr) => curr < pivot);
  // const right = arr.filter((curr) => curr >= pivot);

  const left = [];
  const right = [];

  // Correct but looks the same as my attempt to me
  for (let i = 0; i < arr.length - 1; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }

  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92, 92]));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:157.0) Gecko/20100101 Firefox/157.0

Challenge Information:

Implement the Quicksort Algorithm - Implement the Quicksort Algorithm

GitHub Link: freeCodeCamp/curriculum/challenges/english/blocks/lab-quicksort-js/587d825a367417b2b2512c89.md at main · freeCodeCamp/freeCodeCamp · GitHub

2

Hi @Ninge3007

The difference comes down to one critical detail: the for loop excludes the pivot from the sub-arrays, while your filter approach includes it.

Because the filter method includes the pivot, it fails to shrink the array size during certain splits, leading to infinite recursion and a stack overflow.

Happy coding

3

oooooh I get it now, it was hard for me to imagine it but now I get it.
The for loop manually excludes the pivot in the last place (arr.length - 1) or the first place (i = 1), thank you so much!