InsertionSort mit Generics

Diskutiere InsertionSort mit Generics im Allgemeine Java-Themen Bereich.
Kirby_Sike

Kirby_Sike

Also ich habe die Aufgabe eine generische InsertionSort Methode zu schreiben und stehe auf dem Schlauch xD In der Testumgebung wird keine Java Errormeldung geworfen, sondern es kommt lediglich die folgende Meldung:

Bildschirmfoto 2020-04-06 um 13.57.51.png

Dies kann zum Beispiel an einem Runtime Error liegen (Endlosschleife,....).

Hier ist mal mein Code:

Java:
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        T keyValue;
        int j;
        for(int i = 0; i < list.size(); i++){
            keyValue = list.get(i);
            j = i--;
            while(j >= 0 && list.get(j).compareTo(keyValue) == 1) {
                list.add(j+1, list.get(j));
                j--;
            }
            list.add(j+1, keyValue);
        }
    }
 
H

httpdigest

Hol' dir zuerst einmal eine Desktop-basierte IDE. Dein Programm verursacht vermutlich/vielleicht eine Endlosschleife, der Prozess beendet sich also nicht und somit gibt dir (vermutlich) die Web-basierte IDE diese Fehlermeldung.
 
Kirby_Sike

Kirby_Sike

Hol' dir zuerst einmal eine Desktop-basierte IDE. Dein Programm verursacht vermutlich/vielleicht eine Endlosschleife, der Prozess beendet sich also nicht und somit gibt dir (vermutlich) die Web-basierte IDE diese Fehlermeldung.
Zum coden benutze ich Eclipse :) Ich schreibe mir mal eben einen Testfall und melde mich dann :)
 
J

JustNobody

Ja, gut erkannt. So ist denn die Endlosschleife?

Du hast eine Schleife, in der Du von i = 0 weiter gehst so lange i < list.size() und i wird immer um 1 erhöht.

Und dann fügst Du der List mindestens ein Element hinzu. Aber du nimmst nie ein Element raus.

Also i = 0. Du nimmst das Element mit Nummer 0. Dann ist j nicht größer als 0. Also fügst Du das Element hinzu - und zwar an Stelle 0. 0 -1 + 1 = 0 Wenn die Liste 4 Element hatte, dann hat sie nun 5.

Interessant wird es noch bei der While Schleife ... dann kannst Du noch richtig viele Elemente bekommen :)

Dadurch das Du immer mindestens 1 Element hinzu fügst und i nur um 1 erhöht wird, hast Du eine Endlosschleife.
 
H

httpdigest

i wird sogar wieder um 1 reduziert, bleibt also effektiv immer bei 0:
Java:
        for(int i = 0; i < list.size(); i++){ // <- inkrement
            keyValue = list.get(i);
            j = i--; // <- dekrement!
 
J

JustNobody

Zum coden benutze ich Eclipse :) Ich schreibe mir mal eben einen Testfall und melde mich dann :)
Warum kannst Du das dann nicht testen? Code schreiben ohne jeden Test ist einfach nur Müll. Gleich von Anfang an abgewöhnen. Und es ist doch nun wirklich trivial, da eine kleine Applikation zu schreiben, die eine kleine Liste sortiert um dann das einmal auszuprobieren. Und dann hast Du auch einen Debugger zur Hand um mal Schritt für Schritt zu schauen, was Du da lustiges anstellst!
 
J

JustNobody

i wird sogar wieder um 1 reduziert, bleibt also effektiv immer bei 0:
Java:
        for(int i = 0; i < list.size(); i++){ // <- inkrement
            keyValue = list.get(i);
            j = i--; // <- dekrement!
Ohm das habe ich ganz übersehen ... Hatte ich irgendwie als j = i - 1; gelesen. Dann kann man Kirby gleich noch abwatschen, was er so einen Code schreibt. Goldene Regel - speziell für Anfänger aber auch generell für Clean Code: Incrementor (egal ob pre oder post) immer nur als eigenständiges Statement und wirklich NIEMALS innerhalb einer Zeile.

Es ist ja gut und richtig, das ihr lernt und versteht, wie das funktioniert. Aber nutzt es einfach nicht in eurem Code (es sei denn, es ist explizit verlangt)!
 
Kirby_Sike

Kirby_Sike

Immerhin habe ich jetzt eine Errormeldung xD
Code:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3720)
    at java.base/java.util.Arrays.copyOf(Arrays.java:3689)
    at java.base/java.util.ArrayList.grow(ArrayList.java:237)
    at java.base/java.util.ArrayList.grow(ArrayList.java:242)
    at java.base/java.util.ArrayList.add(ArrayList.java:517)
    at InsertionSort.sort(InsertionSort.java:20)
    at InsertionTest.main(InsertionTest.java:15)
 
Kirby_Sike

Kirby_Sike

Habe es gelöst....Hat jemand ein Brett für mich, welches ich mir vor den Kopf hauen kann? xD Man sollte natürlich die richtige Methode benutzen xD set und nicht add....Ich fühle mich einfach nur dumm xD
 
J

JustNobody

Lol, und als nächstes werde ich meine WBK verlieren, weil ich nun als Gewalttäter abgestempelt werde, der andere wegen Lapalien körperlich angreift :)
 
X

Xyz1

Es empfiehlt sich auch, den konkreten Typ sicherzustellen und nicht mit List<T> list zu hantieren. Falls sich dahinter keine ArrayList verbirgt sollte man in diese umwandeln.
 
J

JustNobody

Warum? Ich sehe kein Problem mit List... Was übersehe ich?
Das frage ich mich gerade. Denn die Implementation gegen ein Interface würde ich sogar als das explizit bessere Design bewerten. Evtl. hat Tobias die Laufzeit des Algorithmus im Blick. Je nach List Implementation könnte es günstiger sein erst eine ArrayList zu bilden damit Zugriffe über die Id schneller sind.

Aber das sind dann Optimierungen... da würde ich ggf den Algorithmus generell überdenken ...
 
H

httpdigest

Da die Callsite sowieso nur monomorphic ist, wird der JIT da direkt die ArrayList-Implementierungen/Methoden aufrufen und kein Dynamic Dispatch durch das Interface machen. Der dabei injizierte Laufzeittyp-Test kann absolut vernachlässigt werden. Es sei denn natürlich, dass die ganze Methode mit etwas anderem als einer RandomAccess List aufgerufen wird. :)
 
Thema: 

InsertionSort mit Generics

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben