Ошибка Stackoverflow в моем алгоритме быстрой сортировки

Я работал над этим кодом несколько дней безуспешно из-за ошибки переполнения стека во время рекурсии.

Проблема заключается в том, что наша точка опоры всегда является 0-м элементом, и с помощью рекурсии мы можем сортировать массив, либо меняя местами, либо создавая новые массивы и копируя их в исходный массив. Я решил создать 2 массива, так как мне их легче понять, но как только я достигаю рекурсивного шага, я получаю эту ошибку.

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

enter code here
public static void main(String[] args) {
    int[] arr = new int[] { 12, 7, 5, 8, 4, 6, 11, 15 };
    quicksort(arr);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();

}



    private static int[] quicksort(int[] arr, int middle) {
    // Base case
    if (arr.length == 1) {
        return arr;
    }
    int[] upper = new int[arr.length];
    int[] lower = new int[arr.length];
    int upperIndex = 0, lowerIndex = 0;

    // Put the elements into their respective pivots
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= middle) {
            lower[lowerIndex++] = arr[i];
        } else {
            upper[upperIndex++] = arr[i];
        }
    }

    // Recurse, and sort the pivots
    lower = quicksort(lower, lower[0]);
    upper = quicksort(upper, upper[0]);

    // Combine lower, middle, and upper back into one array
    System.arraycopy(lower, 0, arr, 0, lowerIndex);
    arr[lowerIndex + 1] = middle;
    System.arraycopy(upper, 0, arr, lowerIndex + 2, upperIndex);
    return arr;
}

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


java recursion sorting algorithm quicksort
person Chakane Shegog    schedule 05.04.2019    source источник
comment
Переполнение стека при переполнении стека   -  person    schedule 06.04.2019
comment
Несмотря на сбивающее с толку сходство имен, Stack Overflow — не очень хороший способ отладки переполнения стека. Вместо этого пошаговое выполнение в отладчике (или даже просто добавление некоторых стратегических операторов печати) поможет вам увидеть, какой прогресс достигается на каждом рекурсивном шаге и почему рекурсия продолжается бесконечно.   -  person manveti    schedule 06.04.2019

Ответы (2)


arrow_upward
0
arrow_downward

Как упоминалось в ответе Куимби, и нижний, и верхний установлены на размер arr.length. Код должен использовать третий параметр, указывающий фактическую длину, например

quicksort(lower, lower[0], lowerIndex);
quicksort(upper, upper[0], upperIndex);

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

Поскольку вы используете отдельные массивы для быстрой сортировки, вы можете рассмотреть трехсторонний раздел:

    public static void quicksort(int[] arr, int pivot, int size) {
        // Base case
        if (size < 2) {
            return;
        }

        int[] upper  = new int[size];
        int[] middle = new int[size];
        int[] lower  = new int[size];
        int upperIndex = 0, middleIndex = 0, lowerIndex = 0;

        // Put the elements into their respective arrays
        for (int i = 0; i < size; i++) {
            if (arr[i] < pivot) {
                lower[lowerIndex++] = arr[i];
            } else if (arr[i] == pivot){
                middle[middleIndex++] = arr[i];
            } else {
                upper[upperIndex++] = arr[i];
            }
        }

        // sort lower and upper
        quicksort(lower,  lower[0], lowerIndex);
        quicksort(upper,  upper[0], upperIndex);

        // Combine lower, middle, and upper back into one array
        System.arraycopy(lower,  0, arr, 0, lowerIndex);
        System.arraycopy(middle, 0, arr, lowerIndex, middleIndex);
        System.arraycopy(upper, 0, arr, lowerIndex+middleIndex, upperIndex);
    }
person rcgldr    schedule 06.04.2019

arrow_upward
0
arrow_downward

Ваши массивы upper и lower, похоже, вообще не уменьшаются, поэтому arr.length == 1 никогда не бывает истинным. Более простая реализация заключается в использовании индексов и только исходного массива.

person Quimby    schedule 05.04.2019