У меня возникли некоторые проблемы со стеком в Java ... Я реализую быструю сортировку с использованием ArrayList - в конце я приложу свой полный код, но вот соответствующие биты (Имейте в виду, я былотлаживать все это в течение нескольких часов, совершенно не зная, что происходит не так, поэтому, если вы видите, что все происходит странным образом и т. д., это более чем вероятно, потому что я пытался найти там ошибки):
Вызов, который, по-видимому, выполняется слишком много раз:
QuickSort(numArray, m+1, right);
Здесь происходит сбой:
//Swap pivot and left
numArray.set(pivot, leftVal);
Я получаю вывод:
Starting sort number: [1] : RandomPivot [ON] : Sorting [RANDOM]
Sorted: 2496 elements.
Took: 53 milliseconds.
Starting sort number: [2] : RandomPivot [ON] : Sorting [RANDOM]
Sorted: 4988 elements.
Took: 25 milliseconds.
Starting sort number: [3] : RandomPivot [ON] : Sorting [RANDOM]
Sorted: 7478 elements.
Took: 49 milliseconds.
Starting sort number: [4] : RandomPivot [ON] : Sorting [RANDOM]
Sorted: 9953 elements.
Took: 85 milliseconds.
Starting sort number: [5] : RandomPivot [ON] : Sorting [RANDOM]
Sorted: 12416 elements.
Took: 131 milliseconds.
Starting sort number: [1] : RandomPivot [ON] : Sorting [SORTED]
Sorted: 2497 elements.
Took: 1 milliseconds.
Starting sort number: [2] : RandomPivot [ON] : Sorting [SORTED]
Sorted: 4984 elements.
Took: 1 milliseconds.
Starting sort number: [3] : RandomPivot [ON] : Sorting [SORTED]
Sorted: 7482 elements.
Took: 2 milliseconds.
Starting sort number: [4] : RandomPivot [ON] : Sorting [SORTED]
Sorted: 9950 elements.
Took: 2 milliseconds.
Starting sort number: [5] : RandomPivot [ON] : Sorting [SORTED]
Sorted: 12424 elements.
Took: 2 milliseconds.
Starting sort number: [1] : RandomPivot [ON] : Sorting [REVERSE SORTED]
Sorted: 2494 elements.
Took: 2 milliseconds.
Starting sort number: [2] : RandomPivot [ON] : Sorting [REVERSE SORTED]
Sorted: 4988 elements.
Took: 10 milliseconds.
Starting sort number: [3] : RandomPivot [ON] : Sorting [REVERSE SORTED]
Sorted: 7470 elements.
Took: 35 milliseconds.
Starting sort number: [4] : RandomPivot [ON] : Sorting [REVERSE SORTED]
Sorted: 9962 elements.
Took: 50 milliseconds.
Starting sort number: [5] : RandomPivot [ON] : Sorting [REVERSE SORTED]
Sorted: 12419 elements.
Took: 65 milliseconds.
Starting sort number: [1] : RandomPivot [OFF] : Sorting [RANDOM]
Sorted: 2497 elements.
Took: 5 milliseconds.
Starting sort number: [2] : RandomPivot [OFF] : Sorting [RANDOM]
Sorted: 4984 elements.
Took: 54 milliseconds.
Starting sort number: [3] : RandomPivot [OFF] : Sorting [RANDOM]
Sorted: 7473 elements.
Took: 47 milliseconds.
Starting sort number: [4] : RandomPivot [OFF] : Sorting [RANDOM]
Sorted: 9958 elements.
Took: 80 milliseconds.
Starting sort number: [5] : RandomPivot [OFF] : Sorting [RANDOM]
Sorted: 12419 elements.
Took: 130 milliseconds.
Starting sort number: [1] : RandomPivot [OFF] : Sorting [SORTED]
Sorted: 2498 elements.
Took: 11 milliseconds.
Starting sort number: [2] : RandomPivot [OFF] : Sorting [SORTED]
Sorted: 4991 elements.
Took: 44 milliseconds.
Starting sort number: [3] : RandomPivot [OFF] : Sorting [SORTED]
Sorted: 7474 elements.
Took: 97 milliseconds.
Starting sort number: [4] : RandomPivot [OFF] : Sorting [SORTED]
Exception in thread "main" java.lang.StackOverflowError
at java.util.ArrayList.set(Unknown Source)
at Sorter.QuickSort(Sorter.java:64)
at Sorter.QuickSort(Sorter.java:107)
at Sorter.QuickSort(Sorter.java:107)
at Sorter.QuickSort(Sorter.java:107)
at Sorter.QuickSort(Sorter.java:107)
(on and on and on and on)
Тестированиеи это всегда терпит неудачу, как только я получаю ~ 7500 как размер моего ArrayList.Всегда терпит неудачу в "ArrayList.set ()", и я не имею ни малейшего понятия, почему.Как видите, все другие отсортированные типы работают нормально с числами, превышающими эту сумму, но с отсортированным списком мне придется вызывать «m + 1, right» n раз, где n - размер списка.
Я пробовал это:
if(m-1>left && m-1<right)
QuickSort(numArray, left, m-1);
if(m+1<right && m+1>left)
QuickSort(numArray, m+1, right);
но я получаю ту же ошибку в любом случае, и я подумал, что легче понять, если она пропущена.
Если я могу увеличить стекразмер, так или иначе, я мог бы отложить ошибку, которая позволила бы мне по крайней мере проанализировать различные методы.
Я запускаю этот код через Eclipse, если это что-то меняет.Спасибо!(Полный код сейчас)
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class Sorter {
//STATE:
public boolean test=false;
public boolean randomPivot=false;
Random r = new Random();
public int sortMethod=1;
public static int RANDOM=1;
public static int SORTED=2;
public static int REVERSE_SORTED=3;
public Sorter(){ }
public ArrayList<Integer> SlowSort(ArrayList<Integer> numArray){
//Add "infinity" to the end
numArray.add(Integer.MAX_VALUE);
//TIME AND RUN QUICKSORT
long startTime = System.currentTimeMillis();
numArray=QuickSort(numArray, 0, numArray.size()-2);
long stopTime = System.currentTimeMillis();
long runTime = stopTime - startTime;
//Remove "infinity" from the end
numArray.remove(numArray.size()-1);
//TODO: Printing effs it up? idk
// printArrayWithMessage("Sort Finished.", numArray);
//PRINT COMPLETION MESSAGE AND RETURN
System.out.println("Sorted: "+numArray.size()+" elements.\nTook: " + runTime+" milliseconds.\n");
return numArray;
}
public ArrayList<Integer> QuickSort(ArrayList<Integer> numArray, int left, int right){
if(left>=right){
return numArray;
}
//Correctly Initialize Pivot
int pivot=0;
if(randomPivot){
pivot = r.nextInt(right-left);
}
pivot+=left;
//Swap pivot and left
Integer temp = numArray.get(pivot);
// System.out.println(numArray.size()+" "+pivot);
int leftVal=numArray.get(left);
numArray.set(pivot, leftVal);
pivot=temp;
numArray.set(left, pivot);
Integer m=0;
//REPEAT:
while(true){
int i=left+1;
int j=right+1;
while(numArray.get(i).intValue()<pivot){
i++;
}
while(numArray.get(j).intValue()>pivot){
j--;
}
if(i<j){
//Swap i and j
if(test) printArrayWithMessage("[SWAP] (i="+i+") and (j="+j+")", numArray);
Integer a=numArray.get(i);
numArray.set(i, numArray.get(j));
numArray.set(j, a);
}
if(i>j){
//Swap pivot and j
if(test) printArrayWithMessage("[SWAP] (j="+j+") and (pivot="+left+")", numArray);
numArray.set(left, numArray.get(j));
numArray.set(j, pivot);
m=j;
break;
}
}
if(test) printArrayWithMessage("Iteration Finished... Left: "+left+" Right: "+right, numArray);
QuickSort(numArray, left, m-1);
QuickSort(numArray, m+1, right);
return numArray;
}
public void benchmark(){
for(int i=1;i<6;i++){
//CREATE BLANK DATA STRUCTURES
ArrayList<Integer> numList = new ArrayList<Integer>();
Set<Integer> doublesFilter;
if(sortMethod==RANDOM){
doublesFilter = new HashSet<Integer>();
}else{
doublesFilter = new TreeSet<Integer>();
}
//FILL ARRAYLIST WITH UNIQUE NUMBERS
for(int j=0;j<2500*i;j++){
int num=r.nextInt(1000000);
if(doublesFilter.add(num)){
if(sortMethod==RANDOM){
numList.add(num);
}
}
}
if(sortMethod==SORTED){
numList.add(0);
numList.ensureCapacity(doublesFilter.size());
numList.addAll(doublesFilter);
numList.remove(0);
}
else if(sortMethod==REVERSE_SORTED){
numList.add(0);
numList.ensureCapacity(doublesFilter.size());
numList.addAll(((TreeSet<Integer>) doublesFilter).descendingSet());
numList.remove(0);
}
System.out.println("Starting sort number: ["+i+"] : "+getMode());
numList=SlowSort(numList);
}
}
public void printArrayWithMessage(String s, ArrayList<Integer> list){
System.out.println(s);
System.out.println(list);
System.out.println();
}
public String getMode(){
String rPivot="OFF";
if(randomPivot) rPivot="ON";
String sortMode="UNDEFINED";
if(sortMethod==1)sortMode="RANDOM";
if(sortMethod==2)sortMode="SORTED";
if(sortMethod==3)sortMode="REVERSE SORTED";
return "RandomPivot ["+rPivot+"] : "+"Sorting ["+sortMode+"]";
}
}