Переполнение стека сортировки и число сравнений и отрицательных свопов - PullRequest
Новая
       10

Переполнение стека сортировки и число сравнений и отрицательных свопов

0 голосов
/ 15 сентября 2011

Я написал эту пузырьковую сортировку и использовал ее в тестовой программе, которая выдает случайные числа в списке на сумму, введенную пользователем. Затем ему был дан список из 10000 случайных чисел, и он вернулся с переполнением стека в строке 55 «if (swaps! = 0) {sort ();}», почему это так. Также иногда это работает, но возвращает значение myCompares и mySwaps, которое является отрицательным. Вы можете помочь? 

public class Bubbly {

    private int[] sortedList;
    private static long myTime = 0;
    private static int myCompares = 0;
    private static int mySwaps = 0;

    public Bubbly(int[] list) {
        sortedList = list;
        StopWatch stop = new StopWatch();
        stop.start();
        sort();
        stop.stop();
        myTime = stop.getElapsedTime();
    }

    public int[] getList(){
        return sortedList;
    }
    public long getTime(){
        return myTime;
    }

    public int getCompares(){
        return myCompares;
    }

    public int getSwaps(){
        return mySwaps;
    }

    public void sort(){
        int length = sortedList.length, i = 0, num, swaps = 0;

        while (i < length - 1){
            if (sortedList[i] > sortedList[i + 1]) {
                myCompares++;

                num = sortedList[i];
                sortedList[i] = sortedList[i+1];
                sortedList[i+1] = num;
                swaps++;
                mySwaps++;
            }
            myCompares++;
            i++;
        }

        if (swaps != 0){
            sort();
        }

    }
}

1 Ответ

2 голосов
/ 15 сентября 2011

Ваша программа рекурсивна, возможно, это первая рекурсивная пузырьковая сортировка, которую я когда-либо видел: -)

Рекурсивность подразумевает, что функция не возвращается, пока работа не завершена, вместо этого каждый раз вызывается метод sort ()дополнительный вызов помещается в стек.И после ряда рекурсивных вызовов стек переполняется и переполняется.

Итак, избавиться от рекурсии здесь не полезно, просто используйте цикл.

Относительно переменных, которые становятся отрицательнымизначения, начните с избавления от статического модификатора на mySwaps, myTime и myCompare, поскольку он препятствует их правильной инициализации при каждом запуске теста.

...