QUICKSORT Algorithm - JavaScript. Im stuck :(

Question

can anybody tell me why this generate infinite loop? Im stuck. Maby i miss something?

const quickSort = function (arr) {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[0];
  const smallerThanPivot = [];
  const highterThanPivot = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      smallerThanPivot.push(arr[i]);
    } else {
      highterThanPivot.push(arr[i]);
    }
  }
  return [
    ...quickSort(smallerThanPivot),
    pivot,
    ...quickSort(highterThanPivot),
  ];
};

Answer 1

It's actually a simple mistake. One trick for me when I started learning Javascript, is to add some console.log to make sure what is happening.

You were starting on position 0. but since zero is already the pivot, you don't need it in the cycle. This was adding one position to the array on every cycle, making it infinite.

This is the correct function

const quickSort = function (arr) {
  if (arr.length < 2) {
return arr;
  }
  const pivot = arr[0];
  const smallerThanPivot = [];
  const highterThanPivot = [];

  /*  //debug prints 
  console.log("Pivot: " + pivot);
  console.log("Length: " + arr.length ); 
  */

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      smallerThanPivot.push(arr[i]);
    } else {
      highterThanPivot.push(arr[i]);
    }
  }
  return [
    ...quickSort(smallerThanPivot),
 pivot,
    ...quickSort(highterThanPivot),
  ];
};