开发者

Sort Stack Overflow and Number of Compares and Swaps Negative

I wrote this bubble sort and used it in a test program that gives random numbers in a list by an amount inputted by the user. It was then given a list of 10,000 random ints and came back with a stack overflow at line 55 "if (swaps != 0){sort();}" why is this. Also at times it works but gives back a value for myCompares and mySwaps that is negative. Can you help?

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(){
       开发者_StackOverflow中文版 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();
        }

    }
}


Your program is recursive, probably the first recursive bubblesort I've ever seen :-)

Recursive implies that the function doesn't return until the work is done, instead each time sort() is called an extra call is pushed onto the stack. And after a number of recursive calls the stack is full and overflows.

So, get rid of the recursion, it's not useful here, just use a loop.

Regarding the variables that get negative values, start by getting rid of the static modifier on mySwaps, myTime and myCompare as it inhibits their correct initialization on each test run.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜