A
A
Artyom Nikolaev2020-05-01 22:23:42
JavaScript
Artyom Nikolaev, 2020-05-01 22:23:42

Stack overflow error in quicksort in JS. How to decide?

const qSort = (arr) =>{
    if(arr.length < 2) return arr; // при пустом массиве или массиве в 1 элемент возвращает его
    let fundam = Math.round(arr.length / 2); // выбираем опорный элемент
    let less = []; //cоздаём массив для элементов меньше опорного
    for(let i = 0; i < arr.length; i++){
        if(arr[i] <= arr[fundam]) {
        less.push(arr[i])
        }

    };
    let greater = [];//cоздаём массив для элементов больше опорного
    for(let i = 0; i < arr.length; i++){
        if(arr[i] > arr[fundam]) greater.push(arr[i]);
    };
    return qSort(less) + arr[fundam] + qSort(greater); 
    
};

When executing this code, it throws a stack overflow error, due to recursion, I can’t find out the reason and therefore I’m asking. An example of quicksort from "Groaking Algorithms.". With an array of 3 elements, the stack is also overloaded, although the function will be called only 3 times.

Answer the question

In order to leave comments, you need to log in

2 answer(s)
R
Rsa97, 2020-05-01
@Quasaru

Look, we feed the array [1, 2, 3]
fundam = Math.round(3 / 2) = 2.
arr[2] = 3
less = [1, 2, 3] as input, since all elements fall into it, less than or equal to 3
greater = []
And again we call sorting the array [1, 2, 3]. Everything is repeated anew. In this case, the number 3 itself will be added to the result again.
First, you need to take not round, but floor.
Secondly, there must be three arrays - less than the reference number, equal to it and greater than it.

const qSort = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const fund = arr[Math.floor(arr.length / 2)]
  let less = []
  let equal = []
  let greater = []
  for (let i = 0; i < 0; i += 1) {
    if (arr[i] < fund) {
      less.push(arr[i])
    }
    if (arr[i] === fund) {
      equal.push(arr[i])
    }
    if (arr[i] > fund) {
      greater.push(arr[i])
    }
  }
  return qSort(less) + equal + qSort(greater)
}

G
galaxy, 2020-05-01
@galaxy

return qSort(less).concat(arr[fundam], qSort(greater));

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question