Sortieren von Objekten innerhalb eines Arrays

Greenkobolt

Mitglied
Nabend Leute,

ich soll für die Uni die folgende Aufgabe lösen:
Wunschliste
Aufgabenstellung
In dieser Aufgabe müssen Sie neben einer Klasse TestWunsch zwei weitere Klassen Wunsch und Wunschliste erstellen. Die Klasse Wunschliste soll hierbei mehrere Wünsche aufsteigend sortiert nach ihrer Priorität mittels eines Feldes vom Typ Wunsch verwalten.
Klasse Wunsch
Die Klasse Wunsch soll genau zwei Attribute (Instanzvariablen) beschreibung (Typ String) und prioritaet (Typ int, je höher der Wert, desto höher ist auch die Priorität) besitzen.
Klasse Wunschliste
Die Klasse Wunschliste besitzt ein Attribut wuensche, welches ein Feld vom Typ Wunsch referenzieren soll. Sie dürfen weitere Instanzvariablen verwenden.
Klasse TestWunsch
Diese Klasse enthält die folgenden drei Methoden:
  • erzeugeLeereWunschliste erhält als Parameter die maximale Anzahl an Wünschen und gibt ein Objekt der Klasse Wunschliste zurück, wobei das Feld vom Typ Wunschbereits mit der korrekten Größe initialisiert wurde (aber noch keine Wünsche enthält).
  • neuerWunsch erhält als Parameter ein Objekt vom Typ Wunschliste sowie einen String (die Beschreibung des Wunsches) und eine Priorität (beliebige ganze Zahle). Sie erstellt einen neuen Wunsch, wobei bei negativer Priorität nur der Wert 0 im Wunsch abgespeichert wird. Der Wunsch soll nun in die Wunschliste eingefügt werden, falls einer der beiden Fälle zutrifft:
    1. es gibt noch eine freie Stelle in dem Feld vom Typ Wunsch
    2. es gibt mindestens einen Wunsch im besagten Feld, der eine geringere Priorität hat (welcher dann auch entfernt wird)
    • Es ist bei dem Einfügen zu beachten, dass die Wünsche zu jedem Zeitpunkt bezüglich ihrer Priorität in aufsteigender Reihenfolge gespeichert werden! Insbesondere darf es zwischen den Wünschen keine Lücken geben.
  • gibWuenscheAus erhält als Parameter ein Objekt vom Typ Wunschliste und gibt alle Wünsche in aufsteigender Reihenfolge zeilenweise im Folgenden Format aus: Wunschbeschreibung (123) (d.h. es wird die Beschreibung des Wunsches gefolgt von der Priorität in Klammern ausgegeben)
Hinweise
Die schwierigste Methode dürfte die neuerWunsch. Es ist hilfreich zuerst eine mögliche Einfügeposition zu finden und dann strikt die beiden Fälle, dass im Feld noch Platz oder das Feld voll ist zu unterscheiden. Wird ein Wunsch eingefügt, muss darauf geachtet werden, dass alle Wünsche bei Index 0 beginnend aufsteigend sortiert sind und zwischen den Wünschen keine Lücken vorkommen. Falls die Wunschliste nicht voll ist, existieren am Ende des Feldes natürlich keine Wünsche (null).
Beachten Sie bei der Sortierung, dass die Wünsche bezüglich ihrer Priorität (hoher Wert = hohe Priorität) aufsteigend sortiert werden. Die Beschriebung spielt diesbezüglich keine Rolle.

Hier direkt erstmal mein momentaner Code:
Java:
public class Wunsch {
     String beschreibung;
     int prioritaet;
}

public class Wunschliste {
    Wunsch wuensche[];
}

public class TestWunsch {
    public static void main(String[] args) {
        Wunschliste b = erzeugeLeereWunschliste(4);
        Wunsch xy = neuerWunsch(b, "Auto", 2);
//        Wunsch xx = neuerWunsch(b, "Hallo", 3);
//        Wunsch xxx = neuerWunsch(b, "Dker", 4);
//        Wunsch xxa = neuerWunsch(b, "P2", 5);
//        Wunsch xax = neuerWunsch(b, "Dhasdf", 1);
        
        
    }
    public static int count = 0;
    public static Wunschliste erzeugeLeereWunschliste (int a) {
        Wunschliste wishList = new Wunschliste();
        wishList.wuensche = new Wunsch[a];
        return wishList;
}
    public static Wunsch neuerWunsch(Wunschliste b, String describe, int prio) {
        Wunsch wish = new Wunsch();
        wish.beschreibung = describe;
        wish.prioritaet = prio;
        if (wish.prioritaet < 0) {
            wish.prioritaet = 0;
        }
        if(count < b.wuensche.length) {
            
            if(b.wuensche[count] != wish) {
                b.wuensche[count] = wish;
                count++;
                
            }
        }
        return wish;
    }
//    public static String gibWuenscheaus(Wunschliste b){
//        String x = "";
//        for(int i = 0; i < b.wuensche.length -count+1; i++) {
//            x += (b.wuensche[i].beschreibung + " " + b.wuensche[i].prioritaet + "\n"); FEHLERHAFT.
//       
//            }
//        return x;
//    }
    

}

Ich habe also die geforderten Klassen Wunsch und Wunschliste erstellt (nach meinem Glauben ist das auch richtig so) und es soweit hinbekommen, dass die Methode "neuerWunsch" dazu führt, dass das Array nicht komplett gefüllt wird, sondern nach der count Variable jeweils nur der Platz.

Das eigentliche Problem:

Das Sortieren nach der Priorität. Ich habe bereits über Comparable oder Comparator gelesen und das ganze auch probiert. Auch mit dem @Override. Sollte ich das richtige gemacht haben, bekomme ich allerdings trotzdem dann jedes mal eine NullPointerException, wenn ich Arrays.sort(b.wuensche); ausführe.

Meine Vermutung ist, dass ich das Array falsch fülle? Wenn ich das, was ich gelesen habe, richtig verstanden habe, kommt es dann zur NullPointerException, wenn das Array "null" ist.

Vielen lieben Dank schonmal
 

Kirby.exe

Top Contributor
Kann man das Problem mit dem Sortieren auch anders lösen? Also ohne ein if?

Java:
if(w.wuensche[w.wuensche.length-1] != null) { // <--------- Den Müll hier
                Arrays.sort(w.wuensche);
                boolean result = Arrays.stream(w.wuensche).anyMatch(wish::equals);
                //System.out.println("result: " + result);
                if(result) {
                    break;
                }else if(w.wuensche[i].getPriority() < wish.getPriority()) {
                    w.wuensche[i] = wish;
                    Arrays.sort(w.wuensche);
                    break;
                }

das Problem dabei ist halt in meinen Augen, dass wenn das Array wünsche eine Größe von 5 hat, dann ist das if erst nach dem 6. Eintrag erfüllt :( Jedoch soll nach jedem Eintrag sortiert werden, wenn man jedoch das löscht dann gibt es eine wunderbare NullPointerException. Ich gehe mal davon aus, dass diese wegen dem Sort von einem nicht Kompleten Array kommt. Meine Frage wäre halt: Wie umgehe ich den Kram? Ich hatte zwar gelesen dass so etwas mit Tree Set oder Hash Maps einfacher geht, was wahrscheinlich auch richtig ist, jedoch müssen wir es mit einem Array vom Typ Wunsch machen(Wunsch [] wünsche).
 

Kirby.exe

Top Contributor
Könnte man hiermit den NullPointer umgehen ?
Java:
Arrays.sort(Object[] a, int fromIndex, int toIndex)
Wenn man einfach bei jedem einlesen einen Counter nimmt und nur bis zu diesem Index sortiert?
 
K

kneitzel

Gast
Du gibst uns ja keine Zeit zum antworten. Ja, das ist eine valide Lösung die Du da gefunden hast. :)

Evtl. nur mal als kleiner Ausblick (womit ich aber dann wohl etwas vorgreife):
- In produktivem Code gehört das Verhalten eines Objektes mit zum Objekt. Also so Klassen bekommen nicht nur die Daten selbst sondern auch die Methoden. Und ein wichtiger Punkt ist dann die Kapselung. Also wie bei einer Waschmaschine: Du nutzt die Bedienungselement. Du wirst nicht auf die Idee kommen, da direkt zu sagen: meineWaschmaschine.Motor.setDrehzahl(xxxx). An dem Beispiel wird auch deutlich, wo die Probleme sind: denn um Beispiele zu nennen: Du musst wissen, wie die Übersetzung ist. Wie viele Umdrehungen beim Motor sorgen für eine Umdrehung der Trommel? Das kenne ich zumindest von meiner Waschmaschine nicht. Und wenn du das wissen solltest: Dann tauscht jemand die Waschmaschine aus und die hat evtl. eine andere Übersetzung ... Also nicht unproblematisch. Daher: Wir nutzen nur, was die Klasse wirklich nach außen bietet und nutzen keine "Innereien".
- Und später wird man bei Dingen, deren Anzahl flexibel ist, in der Regel kein Array mehr verwenden. Statt dessen würde man dann Klassen verwenden, die für eine dynamische Menge an Elementen gedacht sind. In Deinem Beispiel bietet sich z.B. direkt eine ArrayList an und deine Wunschliste könnte ein einfaches
Java:
public class Wunschliste extends ArrayList<Wunsch> {}
(Das ist nur ein Beispiel. Hier muss man genau überlegen, was überhaupt Sinn macht... Da gibt es viele Möglichkeiten und Ideen. Inheritance wie im Beispiel oder Composition - da hätte eine Wunschliste innen eine Instanzvariable vom Typ ArrayList<Wunsch> - nur um da eine Fragestellung / Option anzusprechen.)

Aber da ich da bestimmt einfach nur vorgegriffen habe: Wenn es verwirrend ist, dann vergiss es gleich wieder und warte bis es dran kommt. Aber wenn Du Spaß an der Sache hast und da mehr Zeit investieren willst, dann ist das evtl. auch schon ein interessanter Ansatz, dem Du auch etwas nachgehen könntest.
 

Kirby.exe

Top Contributor
Ich muss noch die andere Übungsaufgabe lösen und dann setze ich mal dran und probiere ein wenig herum :) Ich hatte gelesen dass es damit wesentlich einfacher oder zumindest effizienter funktioniert :)
 

Kirby.exe

Top Contributor
Klar, Du brauchst nur einen Zähler (Instanzvariable) für die Größe. Außerdem lassen sich die Daten effizient verwalten, wenn das Array als Heap organisiert wird.
Ja gut ich habe zwar schon von den Begriffen Stack und Heap gehört, aber ehrlich gesagt keinen Schimmer was du meinst xD

Meine Instanzvariable war einfach der Counter :)
 

mihe7

Top Contributor
Ja gut ich habe zwar schon von den Begriffen Stack und Heap gehört, aber ehrlich gesagt keinen Schimmer was du meinst xD
Jetzt kommt der ausgerechnet mit Stack und Heap daher... Mit Stack und Heap werden sowohl Datenstrukturen als auch Bereiche des Hauptspeichers verstanden. Ich meinte hier die Datenstruktur (hier ein min-heap)

Beim Einfügen wird das neue Element erstmal ans Ende gestellt. Sagen wir mal, das wäre Index i. Anschließend wird mit dem Eltern-Element an Position (i-1)/2 verglichen: hat das eingefügte Element eine niedrigere Prio, werden die Elemente vertauscht. Das wird so lange wiederholt, bis kein Tausch mehr notwendig bzw. möglich ist (weil das Element schon am Anfang des Arrays steht).

Das kleinste Element steht immer an der Wurzel. Um dieses zu entfernen, wird es durch das letzte Element ersetzt, anschließend wird das Element nach unten durchgereicht, indem es mit den Kindknoten (Index 2*i+1 bzw. 2*i+2) verglichen wird. Ist es größer, wird es mit dem kleineren Kindknoten vertauscht. Wiederholung, bis kein Tausch mehr notwendig ist.
 

Kirby.exe

Top Contributor
Ich gehe mal stark davon aus dass wir dies am Ende des Semesters machen werden oder nächstes Semester in Komplexe Algorithmen und Datenstrukturen xD Ich kenn Heap nämlich wie gesagt nur aus dem Hauptspeicher xD
 

Neue Themen


Oben