public T t;
public Elem<T> next;
public Elem() {
this(null, null);
}
public Elem(T t, Elem<T> next) {
this.t = t;
this.next = next;
}
@Override
public int compareTo(Elem<T> other) {
return t.compareTo(other.t);
}
}
public static class List<T extends Comparable<T>> {
public Elem<T> head = new Elem<T>();
public void insert(T t) {
Elem<T> newT = new Elem<T>(t, head);
head = newT;
}
public static <T extends Comparable<T>> void swap(Elem<T> e1, Elem<T> e2) {
T t = e1.t;
e1.t = e2.t;
e2.t = t;
}
public void sort() {
// this = new List<T>(); ist an dieser Stelle nicht möglich
boolean hasChan;
do {
hasChan = false;
Elem<T> e1 = head; Elem<T> e2;
while ((e2 = e1.next).next != null) {
if (e1.compareTo(e2) > 0) {
swap(e1, e2);
hasChan = true;
}
e1 = e2;
}
} while (hasChan);
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//setze(2, 0, 1, 2);
//System.out.println(Math.round(1.1254567 * 100) / 100.0);
List<Character> ls = new List<Character>();
ls.insert('e');
ls.insert('z');
ls.insert(Character.MIN_VALUE);
ls.insert('d');
ls.insert('v');
ls.sort();
Elem<Character> e = ls.head;
while (e.next != null) {
System.out.println(e.t);
e = e.next;
}
}```
Es kann bis jetzt nur vorne eingefügt werden, Elemente entfernen nicht möglich, iterieren nicht möglich, Instanzvariablen public, der bubble sort sortiert in-place, weil ich kann nicht eine Instanzmethode void aufrufen und this etwas zuweisen.
Edit: Das zu schreiben dauert für eine Abi prüfung einfach zu lange (also ich habe lange dafür gebraucht)
Welche Zeile, welcher Code? Zeilennummer immer angeben- oder worauf du dich beziehst. Die Liste muss so gestaltet sein, dass man in der Abi prüfung etwas damit anfangen kann.
Zeile 199. Was meinst du mit “muss so gestaltet sein, dass man in die Pruefung etwas damit anfangen kann?” weil ich koennte damit kaun was anfangen. Das System eines “Pointers” ist total unstaendlich.
Eigentlich heißt es Referenzen, sind aber Pointer, mit denen u.a. nicht gerechnet werden kann.
Es geht vielmehr darum, Zeile 199 lesen und interpretieren zu können.
Ändere mal noch Elem<T> newT = new Elem in Elem<T> newE = new Elem.
Eigentlich wollte ich hier doch gar nix machen
Naja. Es ist ja an dieser Stelle egal, wie die Implementierung aussieht. Sie soll ja nur verwendet werden und so lange Sie funktioniert und die API stabil bleibt ist das zweitrangig, wie das ganze Implementiert ist.
Genausogut hätte man auch nur ein Interface zur Verfügung stellen können. Dann gibt es allerdings das Problem, dass man die eigene Implementierung nicht mehr ausprobieren kann.
Mit den get- und set-Index Methoden hast du die Liste erweitert anstatt Sie zu verwenden. Das ist ein Workaround der zwar funktionieren mag, aber die Lösung anhand der Aufgabenstellung ad absurdum führt.
Zudem ist es ein enormer zeitlicher Vorteil, wenn man sich nicht auf die Implementierung, sondern auf die API/Interface/öffentlichen Methoden konzentriert.
Seh ich wie du, aber ernsthaft: != sollte man kennen. Das ist Grundlage. Mittlerweile habe ich auch die API genutzt wie du es sagst und zur Uebung noch selection und insertion impmelemtiert. Bis auf insertion geht gerade alles…
+1 , bei mir sind z.B. null-Elemente nicht erlaubt, die Implementierung lässt dies allerdings zu
Auf dem Blatt Papier lässt sich das Programm aber auch nicht einfach mal starten. Implementierung kann es neben Schnittstelle ja auch geben, sie wird dann nur versteckt , +1
+1 , das stimmt, damit wäre z.B. auch SelectionsOrt möglich
+1
@groggy : bool & (bool = bool) ↔ hier erfolgt die Auswertung und Zuweisung innerhalb der Klammern auf der rechten Seite innerhalb des Ausdrucks der if-Bedingung immer, denn es ist kein kurzschließendes Und, sondern… („auf Zahl-Typen definierter binärer Bitoperator“ kann es aber auch sein)
@CyborgBeta
Stimmt, daran habe ich nicht gedacht. Ich habe gerade versucht ohne diese “Erweiterung” mit get und set den SelectionSort zu machen, aber irgendwie geht das nicht. Denn es gibt keine Moeglichkeit, die Referenz auf dad aktuelle Objekt eins zurueckzusetzen. Vielleicht uebersehe ich auch was…
Das geht ganz einfach mit getIndex, setIndex und length/size, ist aber wahnsinnig langsam: nn+1/2 hat selsort, mit getIndex/setIndex von LinkedList dann 2n(nn/2), vereinfacht: 2*n³
list = result; ist das Problem, denn das setzt ja eine Klasse einer Listen-Klasse voraus, ich kann in JAVA zwar das, worauf der Zeiger zeigt, verändern, nicht aber den Zeiger selbst
Aaaaber ansonsten ist das super, O(2n) - das ist ja nix
Wünsche angenehme Nacht
Wenn man mal von der Wikipedia ausgeht, dann sollte dies als ein Maxsort, das auch ein Selectionsort ist so oder so ähnlich funktionieren.
while(!list.isEmpty()) {
list.toFirst();
int max = list.getFirst();
list.remove();
while(list.hasAccess()) {
if(max< list.getObject) {
list.insert(max);
max = list.getObject();
list.remove();
} else {
list.next();
}
}
sorted.append(max);
}
return sorted;
//oder alles von sorted zurück zu list kopieren.```
In der List das Maximum suchen und einer neuen Liste hinten anfügen und sogleich aus der ursprünglichen Liste Entfernen.
Dies macht man solange, bis, die Liste leer ist und gibt dann die neue sortierte Liste zurück.
Worauf bezieht sich das? Der Sortieralgorithmus von Landei kann nicht in O(n) laufen, da es bewiesen ist, dass ein Sortieralgorithmus nicht schneller als O(n log n) sein kann. Für Bubblesort gilt eigentlich [tex]O(n^2)[/tex].
Da gibt es nicht so viel zu verstehen. Anstelle alle Elemente immer wieder zu betrachten, wird geprüft ob es in einem Durchlauf eine Vertauschung gab, falls nicht ist das Endergebnis sortiert und es kann aufgehört werden. Der Worst-Case von BubbleSort verbessert sich dadurch jedoch nicht, man gewinnt aber einen Faktor bei vorsortierten Listen. Es gibt noch eine andere BS-Variante welche die Eigenschaft ausnutzt das nach einem Run, alle Elemente rechts der letzten Vertauschung schon sortiert sind.
In meinem Beispiel könntest du die erste for-Schleife genauso mit der flag/do-while-Konstruktion ersetzen. Will man das innere for noch „index-frei“ bekommen geht das nicht ohne weiteres, dazu fehlen Methoden an List die einem helfen würden das bequem zu erledigen. Du wirst also praktisch gezwungen mit einer temporären Liste, wie Landei es getan hat, zu arbeiten. Wahrscheinlich wärst du früher oder später auch auf diese Lösung gekommen.
Es geht um das Speicherplatzverhalten eines Algos, der nicht in-place arbeitet. Erst lesen/denken, dann schreiben. Die Schranke kennt hier bestimmt jeder.
Aja, ich hatte einen Fehler in meiner Berechnung oben: selsort: 2n(n(n+1))/2=2n(n^2+n)/2=(2n^3)/2+(2*n^2)/2=2(n^3+n^2)/2=n^3+n^2
Reiß dich mal zusammen. Dein Verhalten hier ist unter aller Sau. Wenn du die Platzkomplexität meinst, dann schreib das halt dazu. Das kann man auch in einem normalen Tonfall machen und muss nicht gleich rumblaffen. O(n) = O(2n), daher hättest du auch gleich schreiben können „Linearer Platzbedarf“, dann weiß jeder was gemeint ist.
Von Theta hat hier auch niemand geredet - was soll also diese Anmerkung. Mit Wissen „prahlen“, dass du mal was davon gehört hast? Herzlichen Glückwunsch. Ich hatte auch eine Vorlesung „Komplexitätstheorie“…
Anstatt deinen Beitrag zu schreiben hättest du lieber weiter gespielt. Viel Spaß noch.
dich verpflichtet eigentlich auch keiner ;;