Generischer Bubblesort

[Splando]

Hallo zusammen,
ich muss leider nochmals um Hilfe bitte.

Mein Programm soll verschiedene Methoden zum sortieren enthalten.
Allerdings soll es eine generische Klasse sein.
Dahingehend habe ich auf mein Programm mit ArrayLists versehen, was auch geklappt hat.
Jetzt wollte ich im letzten Schritt auf generics umstellen, was sich als deutlich schwierger herausstellt, als gedacht.

Mein Problem: in der Methode bubblesorter möchte ich zwei Einträge aus der ArrayList vergleichen, was mit generics aber nicht mehr geht.
Gibt es hierzu eine einfache Möglichkeit das zu machen?
Oder gehe ich das komplett falsch an? Das bereitet mir mittlerweile echt Kopfschmerzen.
Anbei der Code und vielen Dank

[CODE lang="java" title="Generischer Bubblesort" highlight="33"]package Basics;
import java.util.*;


public class bubblesort <E> {

public E liste;


public ArrayList<E> arrayErstellung(){
int i;
E j;
Scanner sc = new Scanner(System.in);
System.out.println("Wie viele Zahlen moechten Sie eingeben?");
i = sc.nextInt();
ArrayList<E> eingabeListe = new ArrayList<>();
System.out.println("Geben Sie bitte die zu sortierende Werte an:");
//Werte ins Array eintragen
for (int k = 0; k < i; k++) {

j = (E) sc.next();
eingabeListe.add(k, j);
}
return eingabeListe;
}


public ArrayList<E> bubblesorter() {
E a;
ArrayList<E> bubblesortListe = arrayErstellung();
for(int k = 1; k < bubblesortListe.size(); k++){
for (int b = 0; b < (bubblesortListe.size() - k); b++) {
if (bubblesortListe.get(b) > bubblesortListe.get(b+1)) {
a = bubblesortListe.get(b);
bubblesortListe.set(b, bubblesortListe.get(b+1));
bubblesortListe.set(b+1, a);
}
}
}
return bubblesortListe;
}[/CODE]

 

[kneitzel]

Also erst einmal kann das so nicht gehen. Deine generische Klasse kann dann natürlich keine Zahlen eingeben lassen. E kann ja alles sein - was willst Du da Zahlen eingeben?

Und das Sortieren muss dann die Liste, die sortiert werden soll, natürlich als Parameter bekommen.

Der Vergleich selbst kann dann nicht mehr mit > erfolgen. Die Operatoren sind nur für bestimmte Typen definiert. Da gibt es dann zwei Ansätze;
a) Du grenzt E so ein dass E auch Comparable<E> implementieren muss.
b) Der Aufruf nimmt nicht nur die List<E> entgegen sondern zusätzlich noch ein Comparator<E>.

Bei a) kannst Du dann compareTo auf der Instanz aufrufen. Bei b) hast Du das compare vom Comparator, der zwei Instanzen von E nimmt.

 

[Splando]

Ja es alle Zahlentypen eingegeben und sortiert werden.
Eingrenzen bedeudet dann folgendes oder?

[CODE lang="java" title="Eingegrenzte Klasse"]public class bubblesort <E extends Number> {[/CODE]

damit sollte a) eintreten, da nur Zahlen auftauchen?

Kannst du mir bitte noch helfen wie ich compareTo anwende?

Das sind meine ersten Schritte in Java und das überfordet mich gerade etwas

Vielen Dank auf jeden Fall für deine Hilfe.

 

[kneitzel]

Zur Verdeutlichung einfach einmal, wie generische Methoden aussehen könnten:

    public static  <E extends Comparable<E>> void sort(List<E> toSort) {
        // Vergleich ist möglich per
        if (toSort.get(0).compareTo(toSort.get(1)) > 0)
            // ...
            ;

    }

    public static  <E> void sort(List<E> toSort, Comparator<E> comparator) {
        // Vergleich ist möglich per
        if (comparator.compare(toSort.get(0), toSort.get(1)) > 0)
            // ...
            ;
    }

Man sieht die Methodensignatur und wie ein Vergleich innerhalb der Methode aussehen könnte. Es ist natürlich erst einmal keinerlei Sortierung implementiert.

 

[kneitzel]

Es macht aber doch gar keinen Sinn, es auf Number einzugrenzen. Du kannst doch generell alles sortieren, dessen Elemente zu vergleichen kannst.

Und die erste Frage ist: Braucht es eine generische Klasse? Wenn nur eine Methode generisch sein muss, dann reicht es doch aus, dass die Methode generisch ist.

Die Methoden oben kannst Du beliebig Aufrufen. Einige Klassen implementieren bereits Comparable. Integer, String, ...

        List<Integer> list = List.of(5, 4, 7, 8, 3, 2);
        sort(list);
        
        List<String> list2 = List.of("abc", "zxy", "hfg");
        sort(list);

Aber mit dem Comparator kann man z.B. auch vorhandene Implemetationen nutzen. Also z.B. mit einer Klasse Student, die ein Namen beinhaltet:

public class Student {
    private String name;
    
    public String getName() { return name; }
}

Da kann man dann etwas sortieren mit:

        List<Student> students = new ArrayList<>();
        // ...
        sort(students, Comparator.comparing(Student::getName));

==> Es wird also gesagt, dass bei den Student Instanzen die Rückgabe von getName verglichen werden soll.

Das wäre dann eine mögliche Nutzung des skizzierten Codes.

 

[Splando]

Super, vielen Dank. Damit kann ich wieder längere Zeit rumprobieren.

Und ja, es muss eine generische Klasse sein. Das wurde mir in der Aufgabe vorgegeben.
Genau gesagt muss es eine generische Klasse zum sortieren von Objekten sein, für die eine Ordnungsrelation besteht.

Sortiert werden soll mit BubbleSort, QuickSort und SelectionSort, welche ich zum Schluss auf Performance untersuchen soll.



[CODE lang="java" title="sort"]sort(list);[/CODE]

Das ist ja der in Java implementierte QuickSort.

 

[kneitzel]

Genau gesagt muss es eine generische Klasse zum sortieren von Objekten sein, für die eine Ordnungsrelation besteht.

Das hört sich dann nach der ersten Variante mit dem E extends Comparable<E> an und die Variante mit dem Comparator musst Du nicht weiter betrachten.

Wichtig ist aber: Die Sortierung ist generisch. Aber bei den Tests musst Du irgendwas konkretes erstellen um das dann zu nutzen. Also Die Eingabe kannst Du so lassen wie Du willst (um dann eine List<Integer> zu erstellen).

 

[Splando]

Alles klar, nochmals vielen Dank für die Hilfe.
Ich hoffe und denke, dass ich damit weiter komme.
Probieren geht über studieren.

 

[Splando]

Das hört sich dann nach der ersten Variante mit dem E extends Comparable<E> an und die Variante mit dem Comparator musst Du nicht weiter betrachten.

Wichtig ist aber: Die Sortierung ist generisch. Aber bei den Tests musst Du irgendwas konkretes erstellen um das dann zu nutzen. Also Die Eingabe kannst Du so lassen wie Du willst (um dann eine List<Integer> zu erstellen).

Ich würde doch nochmals deine Hilfe brauchen, ich suche schon den ganzen Tag nach einer Lösung.
Meine Methoden habe ich umgeschrieben. Dort bekomme ich auch keinen Fehler.
Folgenden Code habe ich jetzt für den BubbleSort:

[CODE lang="java" title="BubbleSort"]package Assignment;

import java.util.*;

public class SortierKlasse <E extends Number & Comparable <E>> {


private ArrayList<E> liste;


public SortierKlasse() {
liste = new ArrayList<>();
}

public void add(E e) {
liste.add(e);
}

public String getFirst() {
String string = liste.toString();
return string;
}

public static <E extends Comparable<E>> void bubblesort(ArrayList<E> liste) {
E a;
for(int k = 1; k < liste.size(); k++){
for (int b = 0; b < (liste.size() - k); b++) {
if (liste.get(b).compareTo(liste.get(b+1)) > b+1) {
a = liste.get(b);
liste.set(b, liste.get(b+1));
liste.set(b+1, a);
}
}
}
}[/CODE]

Im Main-Programm habe ich dann dann auch mal ein paar Werte erstellt und in die ArrayList geladen. Diese kann ich auch ausgeben lassen.
Nur wenn ich den BubbleSort anwenden möchte hat er ein Problem, dass die generische Methode nicht auf die erstellten Double-Werte anwenden kann. In Zeile 16 im Main beschwert er sich.

[CODE lang="java" title="Main"]package Assignment;
import java.util.*;

public class hauptprogramm {

public static void main(String[] args) {

SortierKlasse<Double> sortierListe = new SortierKlasse<>();


sortierListe.add(5.1125);
sortierListe.add(2.365);
sortierListe.add(1.478);
sortierListe.add(2.789);

SortierKlasse.bubblesort(sortierListe);


System.out.println(sortierListe.getFirst());

}
}
[/CODE]

Was muss ich denn in der Methode noch ändern, dass sie die verschiedenen Typen verwerten kann?
Ich komme leider nicht drauf.

 

[kneitzel]

Die Methode bubblesort nimmt doch eine List<E> und keine SortierKlasse.

Und die Methode zum sortieren ist statisch - also brauchst Du auch keine entsprechende Instanz. Und Wenn in der Klasse die Sortier-Methoden rein sollen: Wozu brauchst Du da ein Instanzvariable mit der Liste?

Dadurch verkürzt sich das dann alles ganz stark:

package Assignment;

import java.util.*;

public class SortierKlasse {
 
    public  static <E extends Comparable<E>> void bubblesort(ArrayList<E> liste) {
        E a;
        for(int k = 1; k < liste.size(); k++){
            for (int b = 0; b < (liste.size() - k); b++) {
                if (liste.get(b).compareTo(liste.get(b+1)) > b+1) {
                    a = liste.get(b);
                    liste.set(b, liste.get(b+1));
                    liste.set(b+1, a);
                    }
                }
              }
        }
}

Den Parameter der Methode kannst Du noch von ArrayList<E> auf List<E> ändern.

Und in dem Hauptprogramm erzeugst Du dann nur eine Liste und gibst die zum sortieren an die Methode.

 

[Splando]

Du hast mein Wochenende gerettet. Vielen Dank.
Jetzt verstehe ich es.

 

[NullCharm]

Den Parameter der Methode kannst Du noch von ArrayList<E> auf List<E> ändern.

Was aber keine gute Idee ist für die Geschwindigkeit

 

[kneitzel]

Was aber keine gute Idee ist für die Geschwindigkeit

Wie beeinflusst das denn Deiner Meinung nach die Geschwindigkeit, wenn man gegen Interfaces entwickelt?

 

[NullCharm]

Hier fehlt eindeutig der Hinweis, bei anderem Typ in eine ArrayList umzuwandeln wenn das halbwegs performant sein soll

Wie beeinflusst das denn Deiner Meinung nach die Geschwindigkeit, wenn man gegen Interfaces entwickelt?

Nichts, ich habe nur etwas gegen schlechten Code oder schlechte Vorschläge. Das musst du ja nicht persönlich nehmen, du kannst entwickeln wie du willst.

 

[kneitzel]

Für den TE an dieser Stelle einfach einmal ein paar Hinweise zu dem "Gegen ein Interface entwickeln", zu dem ich Dir geraten habe.

Der Hintergrund ist eigentlich ganz einfach: Wenn Du gegen ein Interface entwickelst, dann kann Dein Code mit allem Umgehen, was eben dieses Interface implementiert. Das führt dazu, dass Du viel weniger ändern musst, wenn sich der Datentyp z.B, einmal ändern sollte.

Damit wird auch unter dem Strich das abgebildet, das Du an vielen Stellen im Leben siehst:
Du hast nicht einfach einen Führerschein für einen VW Golf. Du hast einen Führerschein für ein Auto. Damit kannst (ok, darfst) Du dann aber alles fahren. Das konkrete Auto spielt da keine Rolle. Es muss nur das Interface "Auto" erfüllen.

Daher sollte man immer so wenig voraussetzen wie nur irgendwie möglich. Was bedeutet das erst einmal konkret?
-> Wenn Du den Parameter ArrayList durch List ersetzt, dann kannst Du da alles übergeben, was eben das Interface List erfüllt. Die ArrayList, die Du füllst, kannst Du also weiterhin übergeben (und das Laufzeitverhalten verändert sich nicht!). Wenn Du aber statt einer ArrayList eine andere List übergeben willst, dann funktioniert das ebenso. Ein konkretes Beispiel wäre z.B. Arrays.asList -> Damit kannst Du ein Array in eine ArrayList umwandeln. Aber Achtung: Das ist nicht Deine ArrayList! Du willst als Parameter eine java.util.ArrayList, aber Arrays.asList liefert eine java.util.Arrays$ArrayList!!!

Generell ist es hier also üblich, sich anzuschauen, was man denn von einem Parameter benötigt.

Im Falle der ArrayList hat man also eine Hierarchie a.la:
ArrayList -> List -> Collection -> Iterable

Iterable wäre super, wenn Du einfach nur über die Menge der Elemente drüber gehen wolltest. Collection ist etwas, das aber noch keine Reihenfolge kennt (Das brauchst du aber natürlich beim sortieren!) Daher wäre hier tatsächlich "List" der Parameter, der genommen werden sollte.

Und die Diskussion mit @NullCharm ignorierst Du einfach. Du musst Dich da nicht von Halbwissen verwirren lassen! Aber ich möchte da doch auch noch etwas zu erwidern -> Das sind dann aber Dinge, die Du erst deutlich später als Thematik bekommen wirst...

Hier fehlt eindeutig der Hinweis, bei anderem Typ in eine ArrayList umzuwandeln wenn das halbwegs performant sein soll

Ja, man kann eine LinkedList oder so umwandeln. Aber um diese entgegen nehmen zu können, müsstest Du erst einmal den Parameter umstellen

Dein schlecht formulierter Punkt ist also vermutlich nur: Wenn jemand schlechte Datentypen verwendet und dann Operationen ausführen will, für die der Datentyp schlecht performt, dann kann das ein Framework evtl. abfangen. Bin ich aber kein großer Fan von - Entwickler sollten Datentypen wählen, die für die Operationen, die sie ausführen wollen, tauglich sind. Und dann bekommt ein Entwicklerggf. mal etwas Nachhilfein SOLID Principles und so

Nichts, ich habe nur etwas gegen schlechten Code oder schlechte Vorschläge. Das musst du ja nicht persönlich nehmen, du kannst entwickeln wie du willst.

Schön, dass Du wieder keine Gründe nennen kannst. Ist Dir das eigentlich nicht peinlich? Aber lassen wir den Punkt. Einfach nur von meiner Seite der dezente Hinweis, dass es sowas wie SOLID Principles gibt mit einem Open Closed Principle.

Aber die Reaktion zeigt: Du warst nur ängstlich, dass dann evtl. schlechte Entwickler auch eher ungeeignete Datentypen über das Interface einreichen könnten und Dir klar ist: Die Änderung des Typs verändert das Laufzeitverhalten in keiner Weise

 

[NullCharm]

Hm, Fehlerbegünstigender Code käme bei mir nicht durchs review.

 

[kneitzel]

Wo begünstigt der Code Fehler?

SOLID Principles über Board werfen? An was für Projekten arbeitest du, dass sowas für dich in Frage kommt?

Und wie sieht dann der Code aus? Nehmen wir dies nur als Beispiel:
Du schreibst das für ArrayList. Jetzt kommt aber jemand mit Arrays$ArrayList daher ... Also doppelten code? Oder umkopieren?

Da würde mich deine Sichtweise nun doch einmal sehr interessieren.

 

[NullCharm]

Naja
public static <E extends Comparable<E>> void bubblesort(List<E> liste) {
würde suggerieren, dass ich jede Liste da reinstecken kann. Und eine LinkedList ist beim "Umverknüpfen" nicht gerade schnell.

Zwei Möglichkeiten: Ich prüfe den konkreten Typ - oder ich schränke die Signatur ein...

 

[kneitzel]

Das suggeriert es nicht nur: dem ist auch so.

Nur eben dem Entwickler obliegt es, geeignete Datenstrukturen zu nutzen. Wenn ein Entwickler eine LinkedList nimmt und die dann sortieren lassen will, dann ist das Problem nicht der allgemeine Algorithmus sonder die Wahl des Entwicklers.

Aber wenn die Prinzipien vernünftig eingehalten wurden, dann ist nur eine Stelle zu ändern: da wo die LinkedList erzeugt wurde, so eine ArrayList sinnvoll ist oder eben die Stelle des Aufrufs.

Aber das ist auch nur dann notwendig, wenn es ein Problem ist. Wenn ich ein Spiel mit x Spielern (x dabei sehr klein, also 10 Spieler oder so) habe, dann ist es einfach egal. Da bemerke ich auch keine LinkedList beim Sortieren um die Reihenfolge anzuzeigen. Der Vorschlag mit dem Umwandeln ist bereits eine Optimierung und die würde ich erst einmal nicht machen.

Bei grundlegenden Libraries ist das ggf denkbar, aber da würde ich das auch eher als ein Feature sehen, das dann erst einmal als solches benannt werden muss.

Das wäre so meine Sicht darauf. Wobei das relativ theoretisch scheint. LinkedList oder so habe ich in freier Wildbahn bisher fast nie gesehen. Da kommt eigentlich immer eine ArrayList oder eben die Immutable List von List.of ins Spiel. (Bei letzteren bekommt man übrigens eine Exception. Ein List.of(...) kann man nicht sortieren.)

 

[Splando]

Danke für die ausführliche Erklärung.
Das ist wirklich sehr hilfreich