bubble sort effizienter machen?

[Cordell]

Hi,

wir haben in der Uni die Aufgabestellung bekommen, dass wir den
Bubblesort-Algorithmus mit Hilfe der nodelist effizienter machen sollen.

Hab nur momentan keinen Plan warum und wieso?

Wäre für Antworten sehr dankbar!

Gruß
Cordell

[Jan Krüger]

Warum ist einfach: er ist lahm. ;)
Da ich aber nicht weiß, was ihr Nodelist nennt, kann ich dazu nichts Weiteres sagen.

[Jidder]

Kann man denn einen Bubblesort-Algorithmus überhaupt effizienter machen? Bleibt nicht egal was man tut die Komplexität bei O(n²), es sei denn man ändert den Algorithmus so, dass er nicht mehr Bubblesort ist? *eine fangfrage vermut* ;)

[etuli]

Naja. Das asympt. Verhalten ist fuer die Praxis oft nicht von Interesse. Frag' mal jemanden nach FibHeaps. Laufzeit toll, Umsetzung haeufig so langsam, dass du schon Mengen an Elementen bringen muesstest, die in der Praxis oft nicht auftauchen. Einfaches Beispiel: A*.

[eViL_oNe]

Hi,

wir haben in der Uni die Aufgabestellung bekommen, dass wir den
Bubblesort-Algorithmus mit Hilfe der nodelist effizienter machen sollen.

Hab nur momentan keinen Plan warum und wieso?

Wäre für Antworten sehr dankbar!

Gruß
Cordell

die einfachste Art und Weise bubblesort effizienter zu machen ist darauf zu verzichten und einen "vernünftigen" O(n log n) Algorithmus zu nehmen *SCNR*

[Jan Krüger]

Naja. Das asympt. Verhalten ist fuer die Praxis oft nicht von Interesse. Frag' mal jemanden nach FibHeaps. Laufzeit toll, Umsetzung haeufig so langsam, dass du schon Mengen an Elementen bringen muesstest, die in der Praxis oft nicht auftauchen. Einfaches Beispiel: A*.
Wenn du eine andere gängige Definition für Effizienz kennst als die asymptotische, immer her damit. :p

[Xpyder]

Ich habe damals (lang ists her) den Bubblesort mal etwas effizienter gemacht. (Anmerkung: Wie schnell oder langsam ein SortierAlgo ist, hängt immer auch von seiner Benutzung ab. Es gibt durchaus Möglichkeiten, in denen er anderen voraus ist.)

Also, der "normale" 08/15 Bubblesort macht ja folgendes:
(Ich definiere mal N = Index des letzten Elements, 0 = Index des ersten Elements. Außerdem gehe ich mal davon aus, daß aufsteigend sortiert werden soll - also kleinstes Element an erste Position.)

Er hat zwei Schleifen, die eine (äußere) läuft rückwärts und gibt die letzte Tauschposition an, diese läuft von N-1 bis 0. Deren Schleifenvariable nenn ich mal A (äußere Schleife). (N-1 deswegen, weil ja immer ein Element und sein Folge-Element verglichen werden. N hat ja kein Folge-Element mehr.)

Die zweite Schleife wird in der ersten Schleife immer wieder ausgeführt und läuft von 0 bis A. Deren Index nenne ich mal X. Jetzt werden ja immer die Elemente an X und X+1 verglichen und wenn nötig (also nicht in richtiger Reihenfolge) getauscht.

Auf die Art "wandert" auf jeden Fall das größte Element bis ans Ende der Liste, also kann die zu sortierende Liste um 1 verringert werden und es wird weitersortiert. (Währenddessen haben aber auch andere Elemente schon ein paar ihrer Plätze getauscht.)

Wenn das ganze Ding durchgeführt wurde, ist die Liste wirklich sortiert.

Und nun die kleine "Optimierung": Allerdings können hier ein paar Durchläufe der äußeren Schleife eingespart werden - und zwar folgendermaßen: Außen wird keine Zählschleife mehr benutzt, sondern nur eine "Grenzvariable". Die nenn ich mal ebenfalls A. (Die wird zu Anfang auf N-1 gesetzt.) Eine Variable T setzt man vor jedem Durchlaufen der inneren Schleife auf -1. In der INNEREN Schleife passiert nun folgendes: Immer, wenn man zwei Werte TAUSCHEN muß, merkt man sich die Position (X), an der man getauscht hat, in T.

Nach Durchlaufen der inneren Schleife verringert man A um 1. Ist T danach noch kleiner als A, so setzt man A auf T, sonst tut man nichts. Danach wird wieder die innere Schleife ausgeführt, usw... Das macht man so lange, bis A=0 (einschließlich) ist, klar. Achso. Sollte nach einer inneren Schleife gleich -1 sein, so kann man natürlich sofort ABBRECHEN, denn wenn nichts mehr getauscht wurde, ist auch nichts mehr zu tauschen, d.h. die Liste ist fertig sortiert!

Was soll der Blödsinn? Nun, es passiert folgendes: Im Prinzip wird genau das gleiche getan wie auch normalerweise - man sortiert die Liste, größter Wert wandert ans Ende, A wird um 1 verringert, nächster Durchlauf - ABER: Wenn ab irgendeiner Stelle nichts mehr getauscht werden mußte, so heißt daß, daß sich ab diesem Ende der Liste nichts mehr ändert, denn sonst wäre ein Wert, der dorthin gehört, ja schließlich auch durchgewandert (und hätte damit T gesetzt). Will sagen: Auf die Art können einige Durchläufe eingespart werden - denn das bereits sortierte Listenende braucht schließlich nicht noch weiter geprüft zu werden.

Zweite "Optimierung": Das gleiche geht auch nochmal (wie man sich sicher schon gedacht hat) für den Listen-ANFANG. Auch hier kann man eine "zuletzt getauscht" Variable (U) für die Position benutzen, nur ist es hier ein wenig komplizierter. Zuerst mal definiert man, daß die innere Schleife von B bis A geht (statt wie bisher von 0 bis A) - damit man diesen Anfang ändern kann.

Außerdem ist diesmal nicht die Position des aktuellen, sondern des vorhergehenden Index' zu "merken" (außer der Index ist 0, klar!), denn es kann durchaus geschehen, daß im Nachhinein Werte dort erscheinen, die "nach vorn" durchgetauscht werden müssen.

Erklärung: Bubble-Sort besiert darauf, Werte quasi "von vorn nach hinten" und "von hinten nach vorn" durchzureichen. Weil aber so eine Zählschleife (wie die innere Schleife) natürlich nur in EINE Richtung gehen kann (in diesem Beispiel vorwärts) ergibt es sich, daß größere Werte vollständig nach hinten wandern, kleinere Werte aber pro Durchlauf nur EINE POSITION nach vorn.

Das bedeutet: Die zweite Grenze (also die "Untergrenze") kann immer hin und her wandern. Sie kann pro Durchlauf einige Positionen vorwärts wandern, sie kann genau da stehenbleiben wo sie war, und sie kann maximal genau um eine Position rückwärts (Richtung 0) wandern.

Hier muß man etwas "geschickt" vorgehen, und zwar so: Man setzt U vor jedem Durchlauf der inneren Schleife auf 0. Wird nun innerhalb der inneren Schleife getauscht, so wird T ganz normal auf den Index (X) gesetzt (siehe oben). U dagegen wird auf X-1 gesetzt, und zwar NUR DANN, wenn X<>0 und U=0 !! (D.h. U wird nur maximal EINMAL pro Durchlauf gesetzt, nämlich an der ERSTEN Tauschposition. Ist U schon <>0, so heißt das, es wurde bereits gesetzt.)

Nach der inneren Schleife wird dann U an B zugewiesen, d.h. das ist die neue Untergrenze für den nächsten Durchlauf.

(Anmerkung: PRAKTISCH setze ich innerhalb der Schleife - wenn getauscht wurde, U auf X, wenn U=0. Außerhalb der Schleife verringere ich dann U um 1, wenn U<>0. Auf die Art erspare ich mir den blöden X<>0 Test innerhalb der Schleife.)

Achso, noch eine kleine DRITTE OPTIMIERUNG: Wenn nach der inneren Schleife (wenn man U noch nicht verringert hat!) T=U ist, weiß man, daß es nur EINE EINZIGE Tausch-Operation gegeben hat - d.h. eigentlich braucht man dann nur noch für den Wert an Position T die richtige Stelle zwischen 0 und T suchen, an der dieser reingehört, d.h. man kann diesen dort einfügen...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Zur "Node-Liste": Hm, keine Ahnung, was gemeint ist. Möglicherweise kann man noch viel mehr optimieren, wenn man ganze Listen von Tauschpositionen anlegt... Aber EIGENTLICH kann ich mir Nodelisten eher bei REKURSIVEN Sortieralgos vorstellen (Quicksort ist z.B. so einer)...

Anmerkung: ICH habe Nodelisten bisher nur bei der Erstellung binärer Bäume benutzt - in binären Bäumen gespeicherte Daten sind ja sozusagen auch "sortiert" - man kann von jedem Element den Vorgänger und Nachfolger bestimmen (und von denen dann wieder deren Vorgänger/Nachfolger), d.h. man kann dann zwar auch bestimmen, wo im Verhältnis zu anderen Elementen sich dieses Element befindet, aber auf eine andere Art (rekursiv halt). Und: Ja, sowas braucht man manchmal.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Aber vielleicht ist das auch nur ein Mißverständnis und es ist etwas anderes gemeint. Wenn ich z.B. so etwas wie DATENSÄTZE sortieren soll, vertausche ich eigentlich nicht die Datensätze SELBST, sondern nur INDIZES auf diese Datensätze.

Das geht wie folgt: Man legt sich zu Anfang eine INDEX-Liste an - das ist ein eindimensionales Array, das genauso groß ist wie die zu sortierende Liste und sortiert dann lediglich die INDIZES (auf der Basis der Datensätze). Ich nenne das Array man INDEX. Mit INDEX[0] bis INDEX[N].

Bevor man sortiert, weist man einfach allen Indizes ihre eigene Position zu, d.h. INDEX[0] enthält den Wert 0, INDEX[1] enthält den Wert 1, ... usw... INDEX[N] enthält den Wert N.

Wenn man sortiert, prüft man nun nicht, ob ELEMENT[X] > ELEMENT[X+1] ist, sondern, ob ELEMENT[INDEX[X]] > ELEMENT[INDEX[X+1]] ist, d.h. man greift indirekt auf die zu sortierenden Elemente zu. Ist das der Fall (also, wenn getauscht werden muß), dann tauscht man aber nicht die Elemente, sondern nur die in INDEX[X] und INDEX[X+1] enthaltenen Zahlen (Indizes).

Nachher hat man dann kein sortiertes Feld, sondern dieses sieht immer noch genauso aus wie vorher. Sondern man hat eine sortierte Index-Liste, und kann über ELEMENT[INDEX[0]] bis ELEMENT[INDEX[N]] aber alle Elemente in der sortierten Reihenfolge abfragen.

Was nun besser ist, entscheidet sich von Fall zu Fall. Hat man z.B. verknüpfte Daten, ist es evtl besser, mit Indexlisten zu arbeiten, da man sonst, wenn ein Datensatz dieses Datenfeldes aus einem Datensatz eines ANDEREN Datenfeldes aus referenziert werden soll, nicht auf dessen Nummer verweisen kann (weil die sich ja beim Sortieren ändern würde!).

Für die Geschwindigkeit des Sortierens SELBST bedeuten Index-Felder: Die Zugriffe auf die Elemente zwecks Vergleich sind natürlich etwas langsamer, da ja INDIREKT auf sie zugegriffen wird. Aber: Das Tauschen geht eventuell schneller, wenn nämlich die zu tauschenden Daten größere Datensätze sind, die umkopiert werden müßten (Indizes dagegen sind ja nur einfache Zahlen).
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Ich habe keine Ahnung, in welcher Programmiersprache das umgesetzt werden soll oder ob es überhaupt auf einen Rechner umgesetzt werden soll, deswegen habe ich es so allgemein und so theoretisch wie möglich beschrieben. Ich hoffe, es ist einigermaßen verständlich geworden.

[Cordell]

Ja schon mal vielen Dank dafür! Das ganze wird in Java realisiert!
Werde mir das morgen mal sorgfältig zu Gemüte führen...

[Cordell]

So hi,

ich hab jetzt etwas mehr Informationen, schon mal vielen Dank für die ausführliche Schilderung!

Es besteht jedoch das Problem den BubbleSort mit Hilfe einer doppelt verketteten Liste effizienter zu machen! Da ich noch relativ neu auf diesem Gebiet bin und mit doppelt verketteten Listen noch nicht viel gemacht habe, fällt es mir schwer den BulleSort damit effizienter zu gestalten.

Was evtl. von Nutzen ist, ist dass die Knoten in der Liste, außgenommen HEAD und TAIL, ihren Vorgänger und Nachfolger kennen.

Ich hoffe mir kann jemand einen Lösungsansatz zu dieser Aufgabenstellung geben.

Gruß
Cordell

[Xpyder]

Ja, damit ähneln sie den Knoten beim binären Baum.
Normalerweise sollten (imo) bei Bubble-Sort eigentlich Hinweise auf den Nachfolger ausreichen, man prüft ja nie den Vorgänger, diese Information wäre also redundant. (Sie könnte auch nachträglich noch hinzugefügt werden.)

Der Witz ist der, daß man beim Sortieren in der inneren Schleife folgendes tut:
a) Man weiß, von welchem Vorgänger man kommt (V).
b) Man kennt die aktuelle Nummer (A).
c) Die aktuelle Nummer hat einen Verweis auf den Nachfolger (N).
- Ist N=ungültig, so ist dieser Sortierdurchgang beendet!
d) Man prüft, ob das Element A größer ist, als das Element N.
e) Ist dem nicht so, geht man zu h)
f) Ist dem so, "sortiert" man, und zwar so:
- Man holt den Nachfolger des Nachfolgers (NN).
- Man setzt den Nachfolger des Elements V auf N.
- Man setzt den Nachfolger des Elements A auf NN.
- Man setzt den Nachfolger des Elements N auf A.
- Man setzt V auf N.
- A bleibt erhalten!
g) Man geht zu a)
h) Hier ist nichts zu tauschen, also tut man nur:
- V wird auf A gesetzt
- A wird auf N gesetzt
i) man geht zu a)

Allerdings - ich kann mir beim besten Willen nicht wirklich vorstellen, inwiefern diese Methode der Methode mit einer normalen Indextabelle (auch indirekt, aber nicht so umständlich) überlegen ist.

Anmerkung1:
Zu Anfang sind die "Nachfolger"-Werte für jeden Knoten so zu setzen: Ist die Knoten-Nummer=X, so wird der Nachfolger auf X+1 gesetzt. Außer beim letzten Knoten, da ist X=ungültig zu setzen. (Das markiert das Ende.)

Anmerkung2:
Wenn man unbedingt für den späteren Bedarf noch einen "Vorgänger"-Wert haben will, so kann man diesen nach dem Sortieren ganz einfach setzen, indem man einmal die ganze Reihe durchhangeln läßt von Knoten zu Knoten und bei jedem Knoten bei "Vorgänger" die Nummer des zuletzt besuchten Knotens einträgt. (Dieser ist zu Anfang auf "ungültig" zu setzen.)

Hoffe, damit kannst Du was anfangen.

Falls Du dagegen lieber mit einem rekursiven binären Baum arbeiten willst, schau mal unter igames.inside1.net/html/dosd3.htm unter "Binäre Bäume", da ist das erklärt. Aber in Binäre Bäume wird eigentlich eher EINSORTIERT, statt nachträgtlich vorhandene Werte umsortiert - deren Knoten haben aber wirklich Vorgänger- und Nachfolger- Felder.

[Cordell]

Vielen vielen Dank Xpyder!!

Das hat mir sehr geholfen! Mit Bäumen hab ich noch nicht so viel gemacht,
kommt aber noch :)

Gruß
Cordell

[Xpyder]

Vielen vielen Dank Xpyder!!
Kein Problem.

Aber, wo ich schonmal da bin:
Ich hatte noch was vergessen! Du hast doch Konstrukte namens HEAD und TAIL erwähnt. Ein TAIL wird hier nicht gebraucht, aber ein HEAD. Dieser ist sozusagen ein Pseudo-Knoten, der kein Element enthält, sondern nur einen "Nachfolger"-Verweis. Der dient dazu, um auf das ERSTE Element im sortierten Feld zu zeigen. Vor dem Sortieren ist er auf 0 (bzw auf die Nummer des ersten Elements) zu setzen. Wenn sortiert wird, ist der HEAD als "Vorgänger" gesondert zu kennzeichnen - d.h. wenn dem Vorgänger-Element etwas zugewiesen werden soll und dieses ist der HEAD, so ist es natürlich dem HEAD zuzuweisen.

Es gibt eine Möglichkeit, das Ganze zu vereinfachen:
Man definiert einfach als erstes IMMER einen Knoten, der ein "Dummy"-Element enthält, das den absolut kleinstmöglichen Wert (bzw einen, der auf jeden Fall immer "vorn" landen würde) enthält. Auf die Art kann man ganz normal sortieren, braucht keinen Extra-Head, sondern startet, wenn man das sortierte Feld durchgeht, immer beim Nachfolger von Element Nummer 0. (Oder 1, oder je nachdem, wo man zu zählen beginnt.) Und man ignoriert den Inhalt dieses Nullten "Dummy"-Knoten. (Der dient nur dazu, damit sein "Nachfolger" Feld den HEAD-Wert enthält.)

[Cordell]

Hi,

also hab jetz schon nen bissel dran gesessen, aber es will nicht so recht
klappen.

Hier mal der Code:


public class Bubble1
{
private NodeList nodelist = new NodeList();
Integer integer = null;

public void sort()
{
int verwendet = 1;
Element ersterKnoten = null;
Element zweiterKnoten = null;
while(verwendet != 0)
{
for(int i = 0; i > nodelist.size(); i++)
{
if(i == 0)
{
ersterKnoten = nodelist.first();
zweiterKnoten = nodelist.next();

}else
{
ersterKnoten = nodelist.next();
zweiterKnoten = nodelist.next();
}

Integer a = (Integer) ersterKnoten.getSpeicher();
Integer b = (Integer) zweiterKnoten.getSpeicher();

if(a.intValue() > b.intValue())
{

Element vorErsterKnoten = ersterKnoten.getVorher();
Element nachZweitenKnoten = zweiterKnoten.getNächste();
vorErsterKnoten.neuesNächsteElement(zweiterKnoten);
nachZweitenKnoten.neuesVorherElement(ersterKnoten);
ersterKnoten.neuesVorherElement(zweiterKnoten);
ersterKnoten.neuesNächsteElement(nachZweitenKnoten);
zweiterKnoten.neuesVorherElement(vorErsterKnoten);
zweiterKnoten.neuesNächsteElement(ersterKnoten);
verwendet++;
}
}
}
}

public void nodeListFüllen()
{
Random ran = new Random();
int laenge = ran.nextInt(25);
for(int i = 0; i <= laenge; i++)
{
Integer integer = new Integer(ran.nextInt(10));
nodelist.addAfter(integer);
}

}

public void ausgabe()
{
Element ausgabe = nodelist.first();
System.out.println(ausgabe.getSpeicher());

for(int i = 0; i < nodelist.size(); i++)
{
ausgabe = nodelist.next();
System.out.println(ausgabe.getSpeicher());
}
}



}


:mauer:

Gruß
Cordell

[Xpyder]

Also, ich hab zwar schonmal bissel PHP gecodet und ein paar einfachere C Quelltexte gesehn usw - aber in Javascript hab ich noch nie was gemacht. (Und auch noch nie selber in C gecodet.)

Und wie genau da jetzt qualifizierte Variablen und Felder funzen, entzieht sich mir leider. (Möglicherweise isses sogar teilweise objektorientiert - damit hab ich auch noch nie was gemacht. Bevor ich da jetzt irgendwas falsches sage, sag ich dazu lieber nix. Mit anderen Worten: Ich bin leider raus.

[Xpyder]

Aber noch was - nicht, daß wir uns da falsch verstanden haben!

Also: NUR der NACHFOLGER (in dem Fall N) gehört wirklich zum KNOTEN!!

A und V sind einfach nur normale Integervariablen, in denen die Nummer des aktuellen und des vorher bearbeiteten Knotens abgelegt sind. Auch die später genannte NN ist nur eine temporäre Integer-Variable!

Das heißt auf meinen Text bezogen: Nur die Nachfolger (in dem Fall also N) gehören zum Knoten dazu!
Ich kann mich irren - aber im Quelltext siehts irgendwie so aus, als hättest Du alle Variablen als Teil der Knoten-"Records" benutzt und nicht nur die Nachfolger.

Zu einem "Knoten" gehören also:
- Das Element selber (also die "Inhalte", die zu sortieren sind.
- Ein Integer-Wert, der die Nummer des Nachfolgers enthält.

Ich könnte mal (ohne Gewähr) versuchen, aus dem Geraffel, was ich da gemacht habe, eine Art C- Code zusammenzuschustern... Aber weiß nicht, ob das wirklich so'ne gute Idee wäre...

[Cordell]

Schade, aber ok!
Achso, es handelt sich nicht um JavaScript, sondern (nur) Java!
:)

Vielleicht kann mir ja jemand anderes weiter helfen.

Gruß
Cordell

[Cordell]

Hi,

hat sich erledigt, bin fertig und es läuft, nochmal vielen Dank für die Antworten!

Gruß
Cordell