Рекурсивные функции работают нормально отдельно, но вместе вызывают ошибку переполнения стека - PullRequest
Новая
       25

Рекурсивные функции работают нормально отдельно, но вместе вызывают ошибку переполнения стека

0 голосов
/ 25 апреля 2018

Работая над проблемой Голландский национальный флаг , я придумал следующий код, надеясь реализовать свой собственный вариант быстрой сортировки: 

static void sort(int[] nums) {
    dutchSort(nums,0,nums.length);
}

// sorts nums[left..right)
static void dutchSort(int[] nums, int left, int right) {
    // recursion base case
    if (left >= right) return;

    int pivot = nums[left];

    // smaller - index of the last element smaller than pivot value
    // equal - index of the last element equal to pivot value
    // larger - index of the first element larger than pivot value
    int smaller = left-1, equal = left, larger = right, temp;

    // before sorting is completed, 'equal' is the current index,
    // much like 'i' in a for-loop
    while (equal < larger) {
        if (nums[equal] < pivot) {
            temp = nums[equal];
            nums[equal] = nums[++smaller];
            nums[smaller] = temp;
        } else if (nums[equal] == pivot) {
            equal++;
        } else {
            temp = nums[equal];
            nums[equal] = nums[--larger];
            nums[larger] = temp;
        }
    }

    // recursively sort smaller subarray
    dutchSort(nums, 0, smaller+1);

    // recursively sort larger subarray
    dutchSort(nums, equal, nums.length);
}

В идеале отсортированный массив должен в идеалесостоят из 3 подмассивов: (i) все значения, меньшие, чем точка, (ii) все значения, равные точке, (iii) все значения, большие, чем точка.Затем подмассивы (i) и (iii) рекурсивно сортируются до тех пор, пока не будет отсортирован базовый случай подмассива размера 1.Я думаю, что мой код делает это правильно, но я не уверен на 100%.Логика в цикле while и значения, используемые для left и right в рекурсивных вызовах, также верны.

Однако два рекурсивных вызова в конце функции dutchSortdutchSort(nums, 0, smaller+1); и dutchSort(nums, equal, nums.length); вызывают ошибку переполнения стека.

Когда я закомментирую обе или только одну из рекурсивных функций, программа завершает работу и создает правильно отсортированный (или частично отсортированный) массив.

Пример ввода (с оба рекурсивные функции закомментированы), включая оператор print для smaller: 

[2,0,1,0,0,2]

Вывод: 

smaller = 3
[0, 1, 0, 0, 2, 2]

Хотя на самом деле это не отсортировано, это все равно правильный выводпоскольку все значения слева от оси являются меньшими значениями.Тогда в идеале две рекурсивные функции будут заботиться о соответствующих подмассивах.В этом конкретном случае необходимо отсортировать только меньший подмассив [0,1,0,0].Обратите внимание, что smaller = 3 правильно показывает, что подмассив из индексов [0..3] должен быть отсортирован.

Перезапуск программы с вводом [0,1,0,0], снова с закомментированными рекурсивными функциями, я правильно получаю: 

[0,0,0,1]

Похоже, логика сортировки верна;исходный массив отсортирован правильно, и ручная сортировка соответствующих подмассивов также работает.Но когда все некомментировано и объединено, есть цикл, который вызывает переполнение стека.

Пожалуйста, помогите мне выяснить причину этого поведения.

Спасибо:)

1 Ответ

0 голосов
/ 25 апреля 2018

Я думаю, что ваш первый рекурсивный вызов должен использовать left в качестве второго параметра: 

dutchSort(nums, left, smaller+1)

вместо 

dutchSort(nums, 0, smaller+1)
...