MergeSort mit Liste

[prime94]

Hallihallo, ich hab' gerade versucht den MergeSort zu implementieren und erhalte immer beim append einen OutOfMemory Error.. Kann zufällig jemand den Fehler in diesen beiden Methoden finden oder liegt es villeicht an der Liste (selbsterstellt nach Abi-Vorgaben) ?

    public List sortieren(List pList){
        Object erstes,letztes;
        pList.toFirst();
        erstes=pList.getObject();
        pList.toLast();
        letztes=pList.getObject();        
        if(erstes==letztes){
            return pList;
        }   
        else{
            List leftList=new List();
            List rightList=new List();            
            pList.toFirst();
            while(pList.hasAccess()){
                leftList.append(pList.getObject());
                pList.next();
                if(pList.hasAccess()){
                    rightList.append(pList.getObject());
                    pList.next();
                }
            }
            leftList= sortieren(leftList);
            rightList= sortieren(rightList);
            return merge(leftList, rightList);
                            
        }
    }
    
    public List merge(List leftList, List rightList){
        List tempList=new List();
        while(!leftList.isEmpty() && !rightList.isEmpty()){
            leftList.toFirst();
            rightList.toFirst();
            if(((Integer)leftList.getObject())<=((Integer)rightList.getObject())){
                tempList.append(leftList.getObject());
                leftList.remove();              
            }
            else{
                tempList.append(rightList.getObject());
                rightList.remove();                
            }
        }
        if(!leftList.isEmpty()){
            tempList.concat(leftList);
        }
        if(!rightList.isEmpty()){
            tempList.concat(rightList);
        }
        return tempList;
    }

Danke
mfG Prime

 

[Michael...]

Hallihallo, ich hab' gerade versucht den MergeSort zu implementieren und erhalte immer beim append einen OutOfMemory Error..

Was ist List für ein Objekt? Scheinbar handelt es sich hier um eine selbsterstellte Klasse. Und wie schaut der append Code aus?

 

[prime94]

Jap, List ist die Datenstruktur lineare Liste selbsterstellt. Hier die 3 Methoden die ich im Sort nutze:
PS: ich weiss dass vieles nicht den effektivsten Weg beschreitet, das ist jedoch momentan für mich zweitrangig!
-> Hab List selbst eigentlich ausführlich getestet. Ein OutOfMemory Error kam nie vor!

    public void append(Object pObject)
    {
        if(pObject!=null)
        {
            if(!isEmpty())
            {
                last.setNachfolger(new Knoten(pObject));
                last=last.nachfolger();
            }
            else{
                first=new Knoten(pObject);
                last=first;
            }
        }
    }

    public void concat(List pList)
    {
        if(!pList.isEmpty())
        {
            pList.toFirst();
            while(!pList.isEmpty())
            {
                append(pList.getObject());
                remove();
                pList.toFirst();
            }
        }
       
    }

    public void remove()
    {
        Knoten temp,temp2;
        if(!isEmpty())
        {
            if(hasAccess())
            {
                if(first==last){
                    first=null;
                    last=null;
                    aktuelles=null;
                }
                else if(aktuelles==first){
                    first=aktuelles.nachfolger();
                    aktuelles=first;
                }  
                else if(aktuelles==last){
                      toFirst();
                      while(aktuelles.nachfolger()!=last)
                          next();
                      aktuelles.setNachfolger(null);
                      last=aktuelles;
                      aktuelles=null;
                }                
                else{
                    temp=aktuelles.nachfolger();
                    temp2=aktuelles;
                    toFirst();
                    while(aktuelles.nachfolger()!=temp2)
                        next();
                    aktuelles.setNachfolger(temp);
                    next();
                }    


            }
        }
    }

 

[SlaterB]

wer soll denn jetzt 50 Zeilen Zeiger-Bewegung + -Verschiebung im Kopf nachprüfen?
wenn du bei dir den Code reproduzierbar zum Fehler bringen kannst, hast du doch alle Möglichkeiten der Welt, auch die Details zu ergründen,
logge zu Beginn jeder Methode, jeder Schleife, jedes Schleifendurchlaufs was passiert,
wenn eine Schleife über 5 Elemente in die 100.000de Runde geht, dann stimmt dort wohl was nicht,
schaue dir die die Bedingung an, schaue die sich verändernde Länge der Listen an usw.

 

[prime94]

Du hast schon recht, dass das nachvollziehen dieses Algorithmusses etwas viel verlangt ist aber ich kann selbst mit Debuggern bisher überhaupt nicht umgehen, daher lag es nahe eine andere Instanz zur Fehlerbehebung anzufragen..