Почему мой размер стека вызовов превышен во время этой быстрой сортировки?

Question

Что не так, когда я пытаюсь реализовать быструю сортировку в JS? Я получаю ошибку превышения размера стека вызовов.

function quicksort(arr) {
  if (arr.length <= 1)
    return arr;
  let pivot = Math.floor(arr.length / 2);
  const left = [], right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 5, 9, 5, 67, 1, 23, 9]));

Answer 1

Когда ваш код строит массивы left и right, этот процесс включает значение разворота. Таким образом, общая длина этих двух подмассивов равна общей длине исходного массива.

Если вы пропустите элемент pivot, тогда сортировка работает (по крайней мере, для вашего теста):

function quicksort(arr) {
  if (arr.length <= 1)
    return arr;
  let pp = Math.floor(arr.length / 2), pivot = arr[pp];
  const left = [], right = [];
  for (var i = 0; i < arr.length; i++) {
    if (i == pp) continue;
    if (arr[i] < pivot) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 5, 9, 5, 67, 1, 23, 9]));

Как я заметил в комментарии выше, одна из ключевых особенностей быстрой сортировки среди других хороших алгоритмов сортировки заключается в том, что она может выполняться с постоянными накладными расходами. Реальные реализации не создают новые подмассивы. Вместо этого они переставляют элементы в исходном массиве. Шаг рекурсии включает начальный и конечный индексы вместо полных новых массивов.

Answer 2

это может быть потому, что длина вашего файла меньше единицы.