Алгоритм быстрой сортировки "StackOverFlowError" - PullRequest
Новая
       36

Алгоритм быстрой сортировки "StackOverFlowError"

1 голос
/ 19 марта 2019

Я реализую алгоритм «QuickSort», предоставляемый через GeeksForGeeks. Я сортирую входной размер случайных чисел 50K, я получаю сообщение об ошибке «StackOverFlowError». Это тот случай, когда рекурсивный вызов не знает, когда достичь своего базового случая? Авария происходит на линии 58. 

int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low-1); // index of smaller element
    for (int j=low; j<high; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;

            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

    return i+1;
}


/* The main function that implements QuickSort()
  arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void sort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is
          now at right place */
        int pi = partition(arr, low, high);

        // Recursively sort elements before
        // partition and after partition
        sort(arr, low, pi-1); // Line 58, on my IDE
        sort(arr, pi+1, high);
    }
}

Ответы [ 3 ]

0 голосов
/ 19 марта 2019

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

Установка на 2 МБ. 

java -Xss2m QuickSort

Если вы используете IDE, измените / добавьте его в «Конфигурация запуска IntelliJ / Ecllipse».

0 голосов
/ 20 марта 2019

Java не сохраняет массивы в стеке. Вместо этого он сохраняет их в куче. Таким образом, вы просто копируете ссылку на массив в куче, а НЕ в массив. И когда вы передаете массивы в методы, вы передаете его по ссылке. Так что на ваш вопрос. У меня та же проблема. А если вы увеличите размер стека, то будет больше времени, чтобы бросить StackOverFlow. Так что это не решение. Если я найду его, я добавлю его сюда.

0 голосов
/ 19 марта 2019

Является ли это случаем, когда рекурсивный вызов не знает, когда достичь своего базового варианта?

Этот метод работает с меньшими массивами.Это не сработает, если не достигнет базового варианта.Итак, нет.

Вы исчерпали размер стека, потому что вы сохраняете копию массива в памяти каждый раз при входе в рекурсию.

...