Question 240568 in Javascript Question posted in
A very good W3school tutorial can be found here.

QUICKSORT Algorithm – JavaScript. Im stuck :(

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),
  ];
};
Tags:

2

Answers


  1. 0

    You don’t filter pivot out from array
    which leads to [1, 2, 3] being split into [], [1, 2, 3] beacuse pivot in placed into a higher part
    Thus the array length is not reducen and you gen infinite loop

    Login or Signup to reply.
  2. 0

    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),
  ];
};
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search