Ошибка переполнения стека в быстрой сортировке на JS. Как решить?

Question

[Артём Николаев]

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

При выполнении данного кода вышибает ошибку о переполнении стека, из-за рекурсии, причину узнать не могу и поэтому спрашиваю. Пример быстрой сортировки из "Грокаем алгоритмы.". При массиве в 3 элемента так же идёт перегрузка стека, хотя функция будет вызвана всего 3 раза.

Answer 1

[Rsa97]

Смотрите, подаём на вход массив [1, 2, 3]
fundam = Math.round(3 / 2) = 2.
arr[2] = 3
less = [1, 2, 3], так как в него попадают все элементы, меньшие или равные 3
greater = []
И снова вызываем сортировку массива [1, 2, 3]. Всё повторяется заново. При этом само число 3 будет добавлено в результат ещё раз.

Во-первых, брать надо не round, а floor.
Во-вторых, должно быть три массива - меньше опорного числа, равные ему и больше него.

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

Comments

[Артём Николаев]

Спасибо большое за пояснение.

Answer 2

[galaxy]

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

Comments

[Артём Николаев]

Нет, такая же ошибка переполнения

[galaxy]

Еще вот это место:

if(arr[i] <= arr[fundam])   ->  if(arr[i] <= arr[fundam] && i != fundam)