Блог

Главная - Вопросы по программированию - Быстрая сортировка, максимальный вызов стека в Javascript

Быстрая сортировка, максимальный вызов стека в Javascript

#javascript #sorting #quicksort

#javascript #сортировка #быстрая сортировка

Вопрос:

Что не так с моим алгоритмом. Это ограничение аппаратного обеспечения, я на старом компьютере, или мой код неправильный? Алгоритм работал оштрафован за вектор с 3,5 тысячами объектов. Теперь я получаю максимальную ошибку стека вызовов при использовании 85 тысяч объектных векторов. Я попытался найти ошибку, но не смог ее найти.

 import { gastos } from './cota-parlamentar-282-mil.mjs';

function quickSort2(vetor, listaPropriedadesOrdenacao) {


    quickSort(vetor, listaPropriedadesOrdenacao[0]);


}

function quickSort(vetor, propriedadeOrdenacao, ini = 0, fim = vetor.length - 1) {

    if (fim > ini) {
        const pivot = fim;

        let div = ini - 1;

        for (let i = ini; i < fim; i  ) {


          //I order the array based on the property specified
            if (vetor[i][propriedadeOrdenacao] < vetor[pivot][propriedadeOrdenacao]) {

                div  
                if (i !== div) {
                    [vetor[i], vetor[div]] = [vetor[div], vetor[i]]
                }

            }
        }
        div  

        if (vetor[pivot][propriedadeOrdenacao] < vetor[div][propriedadeOrdenacao]) {

            [vetor[pivot], vetor[div]] = [vetor[div], vetor[pivot]]


        }



        quickSort(vetor, propriedadeOrdenacao, ini, div - 1)

      //I am getting the error with the line below
        quickSort(vetor, propriedadeOrdenacao, div   1, fim)



    }
}



quickSort2(gastos, ['partido', 'nome_parlamentar', 'id_documento']);

Извините меня за определение имен и прочее, что я просто создаю.

Комментарии:

1. Вы выбираете pivot в качестве последнего элемента в диапазоне, поэтому у вас наихудшее поведение, когда список уже отсортирован или почти отсортирован. Неудивительно, что это проявляется как переполнение стека. Если вы используете это для реального проекта, а не просто изучаете алгоритмы сортировки, тогда вам следует просто использовать встроенную функцию сортировки. Если это академическое упражнение, но вы все равно хотите отсортировать списки из 85 тыс. элементов, выберите сводку случайным образом.

2. Я увеличил максимальный вызов узла с помощью команды node —stack-size = 10000 scriptname.js . Я вызвал его с 280 тысячами, я работал просто отлично!

3. Для наихудшего поведения потребуется глубина стека той же величины, что и размер списка.

4. Можете ли вы включить код, который определяет gastos? Функция быстрой сортировки должна принимать ini и fim в качестве параметров, а не определять их. Эти параметры должны быть определены в функции, вызывающей быструю сортировку.

Ответ №1:

В вопросе недостаточно кода для тестирования, но попробуйте эти изменения:

     quickSort(vetor, listaPropriedadesOrdenacao[0], 0, vetor.length - 1);

...

function quickSort(vetor, propriedadeOrdenacao, ini, fim) {
    while (fim > ini) {
    ...
        if((div - ini) < (fim - div)){
            quickSort(vetor, propriedadeOrdenacao, ini, div - 1)
            ini = div   1
        } else {
            quickSort(vetor, propriedadeOrdenacao, div   1, fim)
            fim = div - 1
        }