Sortierer stürtzt ab

[javakopf]

Moin moin,

ich habe mir einen kleinen Sortieralgorithmus gebastelt. Habe ihn mir selber ausgedacht, kann aber auch sein, dass es den schon unter einer bekannten Variante gibt. Bis 150 Zahlen, die sortiert werden, klappt es. Bei mehr als denen, bekomme ich einen Stack Overflow.

package netbeans.test;

import java.util.*;

public class NetbeansTest {

    public static void main(String[] args) {
        ArrayList<Integer> sortArray = new ArrayList<Integer>();
        for(int i = 0 ; i < 150 ; i++){
            sortArray.add((int)(Math.random() * 2000));
        }
        
        ArrayList<Integer> temp = MasterSort(sortArray);
        System.out.println("FERTIG!");

        for (Integer run : temp) {
            System.out.println(run);
        }

        System.out.println();
    }

    public static ArrayList<Integer> MasterSort(ArrayList<Integer> liste) {
        ArrayList<Integer> totalArray = new ArrayList<>();
        if (liste.size() == 2) {
            if (liste.get(0) < liste.get(1)) {
                totalArray.add(liste.get(0));
                totalArray.add(liste.get(1));
            } 
            else  {
                totalArray.add(liste.get(1));
                totalArray.add(liste.get(0));
            }

            return totalArray;
            
        } 
        else if(liste.size() == 1){
            totalArray.add(liste.get(0));
             return totalArray;
        }
        else if (liste.size() > 2) {
            int gesamt = 0;
            ArrayList<Integer> kleiner = new ArrayList<Integer>();
            ArrayList<Integer> groesser = new ArrayList<Integer>();

            for (int teilzahl : liste) {
                gesamt = gesamt + teilzahl;
            }

            int durchschnitt = gesamt / liste.size();

            for (int teilzahl : liste) {
                if (teilzahl < durchschnitt) {
                    kleiner.add(teilzahl);
                } else {
                    groesser.add(teilzahl);
                }
            }

            ArrayList<Integer> kleinesArray = MasterSort(kleiner);
            ArrayList<Integer> grossesArray = MasterSort(groesser);
            
            totalArray.addAll(kleinesArray);
            totalArray.addAll(grossesArray);
        }
        
        return totalArray;
    }
}

Im Prinzip wird immer rekursiv geteilt - alle Zahlen dir kleiner als der Durchschnitt sind und alle Zahlen die größer sind. Ob das effizient ist oder nicht, weis sich nicht. Ist nur ein Versuch von mir

Fehlercode:

Exception in thread "main" java.lang.StackOverflowError
at java.util.ArrayList.<init>(ArrayList.java:139)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:28)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:65)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
at netbeans.test.NetbeansTest.MasterSort(NetbeansTest.java:66)
...

Ist der Stack-Speicher von Java zu klein? Woran kann das liegen?

Viele Grüße,

javakopf

 

[146532824]

Quicksort ? Wikipedia

 

[SlaterB]

einfach debuggen, kinderleicht zu finden,
anschauen welche Methode mit welchen Parametern aufgerufen wird, hier besonders leicht nur MasterSort(),
schon die Anzahl der Elemente der Liste sagt viel aus,
bei so wenig Elementen kann es zu dem Fehler nur mit einer Endlosschleife immer wieder derselben Elemente kommen oder gar wachsender Anzahl Einträge

hier noch ein Beispiel für eine sehr kleine Liste

        sortArray.add(4);
        sortArray.add(4);
        sortArray.add(5);

nur mit diesen 3 Elementen geht es auch bis unendlich, versuche mal selber herauszufinden warum,
wie sieht der Ablauf richtig aus, was passiert im Programm, wie wird aufgeteilt usw.

mit System.out.println oder Debugger Einzelschritte überprüfen