Methodenkopf

H

Heinrich500

Bekanntes Mitglied
Hallo,
ich will einen Sortieralgorithmus implementieren. Dazu habe ich folgenden Methodenkopf gegeben, den ich nicht ganz verstehe:
Java: 
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Was heißt das genau.
Wenn ich nur
Java: 
public static <T extends Comparable> void sort(List<T> list) {
hätte, dann könnte ich doch Instanzen eines bestimmten Typs T miteinander vergleichen.
Aber was bedeutet das im Kontext mit super T?
 
H

httpdigest

Top Contributor
Das java.lang.Comparable Interface ist auch typparametrisiert. Wenn du nur <T extends Comparable> schreibst, ist nicht sichergestellt, dass ein T in deiner Liste auch Comparable auf sich selbst implementiert. Comparable ist an dieser Stelle dann ein "Raw-Type" und du bekommst Compiler-Warnungen. Da könnten dann auch Listenelement vom Typ:
Java: 
public class ListElementType implements Comparable<String> {
  public int compareTo(String str) {...}
}
drin sein. Die Sortierung muss aber sicherstellen, dass die Elemente auch sich selbst vergleichen können. Das "super" darin sagt dann nur noch, dass ein T nicht "nur" sich selbst vergleichen darf, sondern auch Unterklassen von sich selbst. "super" dann deshalb, weil das erlaubte Typargument von Comparable zumindest T als Supertyp haben muss (darf aber auch abgeleitet sein).
 
H

Heinrich500

Bekanntes Mitglied
Hallo,
ich verstehe nicht, was du damit meinst:
," dass ein T in deiner Liste auch Comparable auf sich selbst implementiert."

wie kann ich dann die compareTo Methode für eine allgemeine Liste von Objekten in der Sortiermethode zum Vergleich verwenden. Im Interface steht ja nur der Rumpf, d,h ich müsste diese implementieren.
Aber wie soll das für den allgemeinen Typ T gehen?
 
H

httpdigest

Top Contributor
Das implementieren die Klassen der Objekte, die du in deiner Sortieren-Methode vergleichen möchtest - also die Objekte in der Liste.
Weißt ja: Polymorphie und Objektorientierung und so...
 
H

Heinrich500

Bekanntes Mitglied
Alles klar:)
Nochmal zu dem super T:
D.h wenn ich eine Klasse Person habe, die Comperable<Person> implementiert. Dann können auch Objekte der Unterklasse Student miteinander verglichen werden?
 
H

httpdigest

Top Contributor
Genauer gesagt, ist dann (und nur dann) möglich, dass eine Oberklasse (also z.B. Person) `Comparable<Person>` implementiert, es eine Unterklasse `Student extends Person` gibt und du trotzdem sort() mit einem `List<Student>` aufrufen kannst, obwohl ja die Klasse Student nicht `Comparable<Student>` implementiert.

In Code ausgedrückt:
Java: 
class Person implements Comparable<Person> {
  public int compareTo(Person o) {...}
}
class Student extends Person {}
public static <T extends Comparable<? super T>> void sort(List<T> list) {
  ...
}
public static void main(String[] args) {
  List<Student> persons = new ArrayList<>();
  sort(persons); // <- funktioniert wegen <? super T>
}

mrBrown hat gesagt.:
Ja, allerdings auch Student mit Professor
Zum Vergrößern anklicken....
Das wäre nur möglich, wenn Student und Professor in einer Vererbungslinie sind, wären sie aber nicht.
 
H

Heinrich500

Bekanntes Mitglied
Aha gut, d.h also egtl, wie man es von der Vererbung kennt, dass die Methode sort() vererbt wird und entsprechend für den Unterklassentyp aufgerufen werden kann. Das ist aber nur in Verbindung mit dem Interface Comparable nur möglich mit dem super T.
Kann man das so sagen?
 
X

Xyz1

Gast
httpdigest hat gesagt.:
<? super T>
Zum Vergrößern anklicken....
Das ist gewissermaßen eine zusätzliche Einschränkung, nicht nur müssen A alle Elems Comparable sein, nein sondern auch alle Comparable Elems müssen B dieselben/ die gleichen (Typ) sein. Damit verhindert man gewissermaßen, Äpfel und Birnen zu vergleichen/ zu sortieren....
Obs sinnvoll ist, sei mal in den Raum gestellt
 
H

httpdigest

Top Contributor
Nein, es handelt sich bei `<? super T>` eben nicht um dengleichen/denselben Typen wie die Typen der Listenelemente. Derselbe Typ wäre nur `<T>`. Wie bereits in dem Beispiel gezeigt, dient `<? super T>` dazu, Vererbung in den Listenelementtypen zu erlauben. T muss nicht `Comparable<T>` implementieren, sondern kann auch von einer Klasse `S` erben, welche `Comparable<S>` implementiert.
Und das ist sehr sinnvoll.
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
httpdigest hat gesagt.:
Das wäre nur möglich, wenn Student und Professor in einer Vererbungslinie sind, wären sie aber nicht.
Zum Vergrößern anklicken....

Ich meinte, dass auch sowas möglich ist:

Java: 
class Person implements Comparable<Person> {
  public int compareTo(Person o) {...}
}
class Student extends Person {}
class Prof extends Person {}


public static <T extends Comparable<? super T>> void sort(List<T> list) {
  ...
}
public static void main(String[] args) {
  List<Person> persons = new ArrayList<>();
  persons.add(new Prof());
  persons.add(new Student());
  sort(persons);
}
 
H

httpdigest

Top Contributor
Tobias-nrw hat gesagt.:
Sinnvoll ist das zudem nur sehr bedingt.
Zum Vergrößern anklicken....
Korrekt. Und die Bedingung ist: true ;)

Spaß beiseite: Es erlaubt dir, eine Liste eines konkreten statischen Typs (wie eben z.B. `List<Student>`) für eine Sortierung zu verwenden, wenn eben nicht Student `Comparable<Student>` implementiert, sondern eine Oberklasse. Wann ist das sinnvoll? Wenn du in einem bestimmten Kontext tatsächlich nur eine Liste von Studenten (und eben nicht Personen) haben möchtest. Du möchtest also statisch sicherstellen, dass die Liste auch nur Studenten und genau Studenten hat. Und für die Sortierung möchtest du jetzt nicht das ganze nochmal statisch casten zu einem `List<Person>`, nur um diese Liste sortieren zu können.
Das `<? super T>` erweitert also die möglichen Typen, mit denen man die Methode aufrufen kann.
 
H

Heinrich500

Bekanntes Mitglied
Ok alles klar.
Ich habe versucht, ein Sortierverfahren mit meinem gegebenen Methodenkopf zu implementieren.
Java: 
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        
       for(int j = 1 ; j < list.size(); j++){
           T elem=list.get(j);
           int i=j-1;
           while(i>0 && (elem.compareTo(list.get(i))<0)){
               list.set(i+1,list.get(i));     
               i--;
           }
           list.set(i+1,elem);
        
       }

Wäre das ok?
 
H

Heinrich500

Bekanntes Mitglied
Das Problem ist, dass ich es nicht kann. In Eclipse werden die Methoden size() und get werden nicht gefunden, obwohl ich das passende importiert habe. Wie kann ich das lösen?
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Das passt so.

Welchen Fehler genau zeigt Eclipse denn an?

Wenn Eclipse nicht will, nimm einfach direkt java (und wenn nötig javac)
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Du hast nicht zufällig noch irgendeinen anderen Import da rumschwirren oder irgendwas im gleichen Package liegen?


Versuchs einfach mal direkt mit java, ohne Eclipse.
 
H

Heinrich500

Bekanntes Mitglied
Ja das war das Problem. Vielen Dank.
Ich habe die Methode getestet, wie folgt:
Java: 
List<Integer> a=new LinkedList<Integer>();
    a.add(3);
    a.add(1);
    a.add(5);
    System.out.println(a);
    sort(a);
    System.out.println(a);

Es wird leider nichts sortiert. Wo liegt denn der Fehler?
 
X

Xyz1

Gast
Heinrich500 hat gesagt.:
Wie kann ich das lösen?
Zum Vergrößern anklicken....
Du musst für den Sotieralgorithmus auch eine implementierung angeben... (Das ist doch Sinn der Sache...)

Mal was verrücktes aus der Versuchskiste: :D

Java: 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ShuffleSort {
    public static void main(String[] args) {
        System.out.println(sort(new ArrayList(List.of(C.c("c"), C.c("a"), C.c("b"), C.c("d")))));
    }

    public static <T extends Comparable<? super T>> List<T> sort(List<T> list) {
        while (!issorted(list)) {
            Collections.shuffle(list);
        }
        return list;
    }

    private static <T extends Comparable<? super T>> boolean issorted(List<T> list) {
        final int N = list.size() - 1;
        for (int i = 0; i < N; i++) {
            if (!(list.get(i).compareTo(list.get(i + 1)) < 0)) {
                return false;
            }
        }
        return true;
    }
}

interface A extends CharSequence, Comparable<CharSequence> { }

abstract class B implements A { }

class C extends B {
    String a;

    public static C c(String a) {
        return new C(a);
    }

    public C(String a) {
        this.a = a;
    }

    @Override
    public int compareTo(CharSequence arg0) {
        return a.compareTo(arg0.toString());
    }

    @Override
    public String toString() {
        return a;
    }

    @Override
    public int length() {
        return a.length();
    }

    @Override
    public char charAt(int arg0) {
        return a.charAt(arg0);
    }

    @Override
    public CharSequence subSequence(int arg0, int arg1) {
        return a.substring(arg0, arg1);
    }
}

Für bereits sortierte Listen ist die Laufzeit super. :D In issorted könnte man bei Verknüpfungen noch einen Iterator hernehmen... hth
 
temi

temi

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

Geht doch deine Code mal gedanklich durch oder verwende einen Debugger und schau dir Schritt für Schritt an, was passiert.

Bei j=1 wird i=0 und damit die while-Schleife überhaupt nicht bearbeitet.
Bei j=2 wird i=1, elem="Element2". In der while-Schleife wird abhängig vom Vergleich das 2. Element auf den Inhalt des 1. Elements gesetzt und nach der while-Schleife wird genau dieses Element wieder auf den Inhalt des ursprünglich 2. Elements gesetzt.
 
H

Heinrich500

Bekanntes Mitglied
Ok dann ist also nicht mein Beispieltestprogramm falsch, sondern die Methode sort() selbst.
Ich habe mich bei der Implementierung an dem Pseudocode für InsertionSort orientiert.
Ich bin es nochmal durchgegangen.
Ich kann den Fehler einfach nicht finden?
 
X

Xyz1

Gast
Heinrich500 hat gesagt.:
Ich kann den Fehler einfach nicht finden?
Zum Vergrößern anklicken....
hallo nochmal,
InsertionSort?, der Pseudocode auf Wikipedia (deutsch) ist ja schrecklich, da finde ich SelectionSort angenehmer... das ist aber auch nicht so wichtig. Ich habe das jetzt einmal gemacht, aber die anderen musst Du alle machen. So KANN eine implementierung schauen:
Java: 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class InsertionSort {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>(List.of(
                "b",
                new String("c")/*pooling :(*/,
                new String("c"),
                "a")/*immutable*/)/*de-immutable*/;
        Collections.shuffle(list);/*demonstrate*/
        System.out.println(list);
        for (String s : list) {
            System.out.println(System.identityHashCode(s/*statically-typed :(*/));
        }
        System.out.println(sort(list));
        for (String s : list) {
            System.out.println(System.identityHashCode(s));
        }
    }

    public static <T extends Comparable<? super T>> List<T> sort(List<T> list) {
        Comparable[] a = new Comparable[list.size()];/*generic array creation :(*/
        for (int i = 0; i < list.size(); i++) {
            a[i] = list.get(i);
        }

        for (int i = 1; i < a.length; i++) {
            Comparable c = a[i];
            int j = i;
            for (; j > 0 && c.compareTo(a[j - 1]) < /*stable/stabil*/ 0; j--) {
                a[j] = a[j - 1];
            }
            a[j] = c;
        }

        list.clear();
        for (Comparable c : a) {
            list.add((T)/*safe*/ c);
        }

        return list;
    }
}


Bis dann.
 
H

Heinrich500

Bekanntes Mitglied
Hallo,
Danke für deine Antwort. Ich verstehe deinen Code auch.
Aber warum geht den mein Programm nicht.
Ich würde gerne den Fehler beheben, auch wenn der Pseudocode als Vorlage nicht der beste ist :)
Kann mir da jmd weiterhelfen?
 
mihe7

mihe7

Top Contributor
Dein Code sortiert schon, allerdings erst ab dem 2. Element (bei 3,1,5 ändert sich also nichts, weil 1,5 bereits sortiert ist; wenn Du 3,5,1 als Liste verwendest, wirst Du sehen, dass 3,1,5 rauskommt). Grund: Deine while-Schleife geht nicht bis zum ersten Element (siehe Kommentar #31 von @temi). Das ist alles.
 
mihe7

mihe7

Top Contributor
i >= 0 ist richtig (in seinem Code, s. Kommentar #18), denn auch das erste Element muss ggf. nach hinten verschoben werden, falls es größer als das "einzufügende" ist.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Was bedeuten die Drei Punkte in einem Methodenkopf? Java Basics - Anfänger-Themen 3
K Warum deklariert man Variablen in Methodenkopf? Java Basics - Anfänger-Themen 6
Helgon Polymorphie Generischer Methodenkopf - Erklärung Java Basics - Anfänger-Themen 3
K Probleme mit den Methodenkopf Java Basics - Anfänger-Themen 8
M Problem mit Array in Methodenkopf Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben