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.
精彩评论