BubbleSort StackOverflowError

Question

Dodałem ten algorytm rekursywny BubbleSort do mojej gry, która działa na lwjgl. Próbuję posortować ArrayList obiektów "Cloud" przez float, który jest prędkością tej chmury.

Z jakiegoś powodu czasami otrzymuję "java.lang.StackOverflowError" w wierszu, w którym sam wywołuję metodę.

Oto kod:

public void sort() { 
    for (int i = 0; i < clouds.size() - 1; i++) { 
     Cloud cl1 = clouds.get(i); 
     Cloud cl2 = clouds.get(i + 1); 
     if (cl1.getSpeed() < cl2.getSpeed()) { 
      continue; 
     } 
     clouds.set(i, cl2); 
     clouds.set(i+1, cl1); 
     this.sort(); 
    } 
} 

I tu są błędy Dostaję:

Sat May 04 20:28:45 CEST 2013 ERROR:null 
java.lang.StackOverflowError 
     at backgrounds.Clouds.sort(Clouds.java:224) 
[...] // The line above is repeated for some hundred times. 

Answer 1

, co dzieje się, gdy dwa kolejne chmury mają taką samą prędkość.

cl1.getSpeed() < cl2.getSpeed() 

jest fałszywa, więc zamieniłem się chmury i sort nazywa się ponownie. W tej rozmowy

cl1.getSpeed() < cl2.getSpeed() 

nadal jest fałszywy, więc znowu zamienić i nazywają sort. To trwa wiecznie (lub lepiej: dopóki stos jest pełny).

Zmień < na <= i wszystko powinno działać poprawnie.

Answer 2

To może być lepiej użyć wbudowanej metody sortowania dla tablic w Javie Arrays.sort() używać to wszystko, co musisz zrobić, to zastąpić metodę porównywania z metodą. Oto jak to wygląda.

@Override 
public int compareTo(Book other) { 
//compare logic here 
} 

Należy także wdrożyć Porównywalne to zrobić

Answer 3

możliwość porównania logika powinna przejść dwa chmurze obiektów, jeżeli są one same też -

zmienić, jeśli do -

if (cl1.getSpeed() <= cl2.getSpeed()) { 
    continue; 
} 

Answer 4

To może być dalej zoptymalizowany jako

public void sort() { 
    boolean swaps = false; 
    for (int i = 0; i < clouds.size() - 1; i++) { 
     Cloud cl1 = clouds.get(i); 
     Cloud cl2 = clouds.get(i + 1); 
     if (cl1.getSpeed() <= cl2.getSpeed()) { 
      continue; 
     } 
     swaps = true; 
     clouds.set(i, cl2); 
     clouds.set(i+1, cl1); 
    } 

    //Re-Iterate all the elements only if a swap is found 
    if(swaps) 
     this.sort(); 
} 

Answer 5

częstą przyczyną dotyczący przepełnienie stosu jest złym rekursywnym wywołaniem, które powstaje, gdy funkcje rekursywne nie mają poprawnego warunku zakończenia, więc kończy się ono wywoływaniem na zawsze. W twoim przypadku warunek zakończenia nie jest spełniony ze względu na znak "<", więc musisz zmienić to na "< =" to wszystko.