Почему эта функциональная версия QuickSort прерывается? И как мне это исправить?

Question

Эта реализация сносит стек на массив любого размера:

function quickSort(arr){ 

    let pivot = arr[arr.length-1] 

    return quickSort(arr.filter((num) => (num < pivot))) 
    .concat(quickSort(arr.filter((num) => (num >= pivot)))) 
} 

Почему это не работает? Если это можно исправить, как мне это сделать?

Answer 1

Представьте, что массив уже отсортирован, например. [3]. Сводка будет 3, а две рекурсии будут [] и [3]. Опорный элемент для [] равен undefined, но это не позволяет ему фильтровать больше или меньше, чем undefined, что совершенно нормально, поскольку предикат никогда не будет проверен с помощью массива нулевого элемента. Оба фильтра становятся [], и вы получаете две рекурсии с [] от одного.

quickSort([])   // ==> 

quickSort([]) 
.concat(quickSort([])) // ==> 

quickSort([]) 
.concat(quickSort([])) 
.concat(quickSort([])) // ==> 

quickSort([]) 
.concat(quickSort([])) 
.concat(quickSort([])) 
.concat(quickSort([])) // ==> 

... (expands forever on an infinite space machine) 

Уведомление: Я просто расширяюсь до первого слева, так как правую руку вы никогда не достигнете.

Так что quicksort не сортирует массив с одним или менее элементами. В этом случае у вас есть базовый регистр, который просто возвращает массив как есть.

У вашей реализации все еще есть проблема. Представьте себе сортировку [3 3 3] вы в конечном итоге с [] и [3 3 3] каждый раз. Традиционно опорная точка устанавливается между двумя отсортированными массивами и не включается в последнюю. Таким образом, у вас есть худший случай quicksort, но рабочее решение.

О Quicksort is required to be in-place

Quicksort, как определено Хоара в своем основополагающем документе, является алгоритм на месте. Разделение на месте Хоара - основной вклад его статьи и важнейшая часть быстрой сортировки.