Prinzip-Erläuterung von BubbleSort dringend benötigt!

[Rayne]

Prinzip-Erläuterung von BubbleSort dringend benötigt!

Hallo!

An sich verstehe ich schon, wie BubbleSort funktioniert.
Jedoch tue ich mich schwer bei der genauen Erläuterung des Struktogrammes.

Habe hier mal ein Struktogramm und Beispiel für BubbleSort:

http://www.sky-divezone.de/Other/Sort.jpg

Also die äußere Schleife durchsucht ja das gesamte Array von hinten nach vorne durch und die innere Schleife ist für die Tauschvorgänge verantwortlich, richtig?

Nur begreife ich nicht wirklich diese Schreibweisen wie "von (1) bis (n-1) ?(
Was soll das darstellen? Dieses "(n-1)" bedeutet ja sicherlich, dass das Programm von hinten anfängt (also 5) und sich dann immer um eine Stelle weiter nach vorne bewegt und dort die beiden Zahlen miteinander vertauscht, oder? Aber was bedeutet diese "(1)"?

Noch schlimmer wirds ja bei der zweiten Schleife
Wieso ist "i=(n-1)"? Und wie muss ich die Vorgehensweise "von (-1) bis j" verstehen?

Am Hilfreichesten wäre es, wenn mir jemand die Schrittfolge von Anfang bis Ende genau erklären könnte mit besonderem Bezug auf die verwendeten Variablen.

Vielleicht ist es einfacher als gedacht, aber mit logischem Verstehen tue ich mich ab und zu etwas schwer

Danke für jede Hilfe!

Rayne

 

[bigmike83]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Hallo!

An sich verstehe ich schon, wie BubbleSort funktioniert.
Jedoch tue ich mich schwer bei der genauen Erläuterung des Struktogrammes.

Habe hier mal ein Struktogramm und Beispiel für BubbleSort:

http://www.sky-divezone.de/Other/Sort.jpg

Also die äußere Schleife durchsucht ja das gesamte Array von hinten nach vorne durch und die innere Schleife ist für die Tauschvorgänge verantwortlich, richtig?

Nur begreife ich nicht wirklich diese Schreibweisen wie "von (1) bis (n-1) ?(
Was soll das darstellen? Dieses "(n-1)" bedeutet ja sicherlich, dass das Programm von hinten anfängt (also 5) und sich dann immer um eine Stelle weiter nach vorne bewegt und dort die beiden Zahlen miteinander vertauscht, oder? Aber was bedeutet diese "(1)"?

Noch schlimmer wirds ja bei der zweiten Schleife
Wieso ist "i=(n-1)"? Und wie muss ich die Vorgehensweise "von (-1) bis j" verstehen?

Am Hilfreichesten wäre es, wenn mir jemand die Schrittfolge von Anfang bis Ende genau erklären könnte mit besonderem Bezug auf die verwendeten Variablen.

Vielleicht ist es einfacher als gedacht, aber mit logischem Verstehen tue ich mich ab und zu etwas schwer

Danke für jede Hilfe!

Rayne

Hallo,

ich find das Struktogramm auch ein bisschen unübersichtlich aber ich versuch mal es zu erklären:

Der äußere Schleife läuft von 1 bis n-1, da n (die Arraygröße) in diesem Fall 5 ist (der Array beinhaltet 5 Elemente, mit Indizes 0-4) wird j mit den Werten 1 bis 4 belegt (dh. im ersten Durchlauf 1, dann 2 etc.).

In der inneren Schleife startet i bei n-1 (also 4) und wird dann bei jedem Durchlauf um 1 verringert bis der aktuelle Wert von j erreicht ist.

Im ersten Durchlauf der beiden Schleifen würde das Folgendes bedeuten:
j hat den Wert 1, in der inneren Schleife startet i mit 4. Also wird a3 mit a4 verglichen, da a3 nicht größer als a4 ist ändert sich nichts. Im nächsten Durchlauf der inneren Schleife hat i den Wert 3, also wird a2 mit a3 verglichen, da a2 größer ist werden die beiden vertauscht. Im nächsten Durchlauf der inneren Schleife hat i den Wert 2, also wird a1 mit a2 verglichen, da a1 größer ist werden die beiden vertauscht. Im nächsten Durchlauf der inneren Schleife hat i den Wert 1, also wird a0 mit a1 verglichen, da a0 größer ist werden die beiden vertauscht.

Da i jetzt den gleichen Wert wie j hat, ist der erste Durchlauf der äußeren Schleife beendet. Daher wird j auf 2 erhöht, und die innere Schleife startet wieder mit i=4. Da in diesem Fall j bereits 2 ist, bricht die innere Schleife nach dem Durchlauf mit i=2 ab (dh. i bekommt die Wert 4, 3, 2).

EDIT:

Hier noch die Variablenbelegungen für jeden Durchlauf der inneren Schleife (die Zahl gibt die Nummer der äußeren Schleife an, der Buchstabe die Nummer der inneren):
1a: j = 1, i = 4
1b: j = 1, i = 3
1c: j = 1, i = 2
1d: j = 1, i = 1
2a: j = 2, i = 4
2b: j = 2, i = 3
2c: j = 2, i = 2
3a: j = 3, i = 4
3b: j = 3, i = 3
4a: j = 4, i = 4

Naja, ich hoffe ich konnte dir ein wenig helfen, es ist für mich irgendwie nicht so einfach solche Diagramme leicht verständlich zu erklären

Gruss
bigmike

 

[olstyle]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Das ist mal was anschauliches :
http://olli.informatik.uni-oldenburg.de/fpsort/Animation.html
BubbleSort ist sowieso fürn Popo, min- bzw. maxSort ist einfacher zu verstehen und auch effektiver.
mfg Olstyle

 

[Rayne]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Danke Leute, ich glaub, ich habs begriffen )

Hab das Struktogramm noch ein wenig umgeschrieben:

http://www.sky-divezone.de/Other/Sort2.jpg

Falls mir doch noch etwas unklar erscheinen sollte, melde ich mich nochmal, versprochen

@bigmike83: Wie würdest du das Struktogramm denn aufstellen?

Rayne

 

[bigmike83]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Danke Leute, ich glaub, ich habs begriffen )

Hab das Struktogramm noch ein wenig umgeschrieben:

http://www.sky-divezone.de/Other/Sort2.jpg

Falls mir doch noch etwas unklar erscheinen sollte, melde ich mich nochmal, versprochen

@bigmike83: Wie würdest du das Struktogramm denn aufstellen?

Rayne

Hallo,

ich denke jetzt ist es schon mal sicher leichter verständlich, ich würde so was in der Richtung machen:

j = 1
Solange j <= n-1
i = n-1
Solange i >= j
sortieren
i = i - 1
j = j + 1

Das wär dann mehr der programmiernahe Ansatz, ich denke es kommt aber sicher auf die Vorkenntnisse an mit welcher Variante man sich besser zurechtfindet...

Naja, ich denke die beste Variante ist die mit der du dich am besten zurechtfindest

Gruss
bigmike

 

[Rayne]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Hallo,

ich denke jetzt ist es schon mal sicher leichter verständlich, ich würde so was in der Richtung machen:

j = 1
Solange j <= n-1
i = n-1
Solange i >= j
sortieren
i = i - 1
j = j + 1

Das wär dann mehr der programmiernahe Ansatz, ich denke es kommt aber sicher auf die Vorkenntnisse an mit welcher Variante man sich besser zurechtfindet...

Naja, ich denke die beste Variante ist die mit der du dich am besten zurechtfindest

Gruss
bigmike

Danke für deine Ansätze, haben mir sehr weitergeholfen

Rayne

 

[Rayne]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

So, ich gibt wieder ein paar Unklarheiten

Diesmal gehts aber nicht nur um BubbleSort, sondern um den Vergleich von einfachen und komplexen Sortierverfahren.
Ich dachte, ich eröffne nicht extra einen neuen Thread dafür und schreibe meine Frage hier rein.

Man sieht ja anhand vieler Zeitmessungen im Netz, dass Verfahren wie QuickSort, Mergesort und SelectionSort schneller arbeiten, als beispielsweise BubbleSort.

Aber wie erkläre ich jetzt genau, dass die komplexen Sortierverfahren schneller arbeiten, als das einfache?

Habe mir zwar die Funktionsweisen der genannten Algorithmen angesehen, aber richtige Begründungen für etwaige Zeitunterschiede habe ich nicht gefunden.

Es gibt zwar diese Angaben für die Zeitkomplexität (n² bzw. n*log n), aber das als Begründung dürfte nicht ausreichen.

Vielleicht kennt ihr die Begründungen?

Wäre nett.

Rayne

 

[olstyle]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

So, ich gibt wieder ein paar Unklarheiten

Diesmal gehts aber nicht nur um BubbleSort, sondern um den Vergleich von einfachen und komplexen Sortierverfahren.
Ich dachte, ich eröffne nicht extra einen neuen Thread dafür und schreibe meine Frage hier rein.

Man sieht ja anhand vieler Zeitmessungen im Netz, dass Verfahren wie QuickSort, Mergesort und SelectionSort schneller arbeiten, als beispielsweise BubbleSort.

Aber wie erkläre ich jetzt genau, dass die komplexen Sortierverfahren schneller arbeiten, als das einfache?

Habe mir zwar die Funktionsweisen der genannten Algorithmen angesehen, aber richtige Begründungen für etwaige Zeitunterschiede habe ich nicht gefunden.

Es gibt zwar diese Angaben für die Zeitkomplexität (n² bzw. n*log n), aber das als Begründung dürfte nicht ausreichen.

Vielleicht kennt ihr die Begründungen?

Wäre nett.

Rayne

Bubblesort hat den Hauptnachteil, dass es in jedem Durchgang physikalisch Werte vertauscht , dabei wird z.B. bei einem Feld wie diesem:
10,9,8,7,6,5,4,3,2,1
die 10 ganze 9 mal umgeschrieben bevor sie am eigentlichem Ziel angekommen ist.
Diesem Nachteil stellt sich das schon oben genannte Min/Maxssort entgegen indem es erst schreibt wenn es weiß wo der Wert genau hin gehört.
Das System hat aber immernoch das Problem, dass immer jede Zahl mit Jeder verglichen werden muss.
Quicksort setzt wiederum dort an und behebt dass Problem indem es das Feld zerstückelt und immer nur mit einer Zahl vergleicht.

Wenn wir hier grad am sortieren sind kann mir doch sich einmal jemand sagen warum dieser Teil von Quicksort nicht aus der Schleife raus kommt:

private void quicksort(int links,int rechts)
{
int pivot=zahl[rechts];
int linkerIndex=links;
int rechterIndex=rechts;

while(linkerIndex<=rechterIndex)
{


while(zahl[linkerIndex]<pivot)
{linkerIndex++;
}

while(zahl[rechterIndex]>pivot)
{rechterIndex--;
}
int temp = zahl[linkerIndex];
zahl[linkerIndex] = zahl[rechterIndex];
zahl[rechterIndex] = temp;

}
System.out.println("einmal durch die Schleife");
}

Das "einmal durch die Schleife" dient zur kontrolle, wird aber nie ausgegeben.

mfg Olstyle

 

[Rayne]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Danke für die Antwort

Mich würde jetzt noch interessieren, wie denn so eine Abbruchbedingung für BubbleSort aussehen könnte.

Ich habe da mal was ausprobiert, bin mir aber nicht sicher, ob das so geht.

Das Ding soll bedeuten, dass, wenn in der inneren Schleife keine Vertauschungen mehr stattgefunden haben, das Programm stoppt, anstatt ewig weiterzulaufen.

http://www.sky-divezone.de/Other/bubble.gif

Vielen Dank!

Rayne

 

[Rayne]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

OK, wie das mit der Abbruchbedingung funktioniert, habe ich mittlerweile rausgefunden.

Aber ich habe so meine Probleme, ein vernünftiges PAP (Programmablaufplan) für Bubblesort zu erstellen

Weiß hier jemand zufällig, wie das richtig aussehen müsste und könnte mir eventuell eine Skizze davon schicken?

Wäre wirklich sehr nett

Danke!

Rayne

 

[sdmayday]

AW: Prinzip-Erläuterung von BubbleSort dringend benötigt!

Vergiss bitte Bubble Sort - das ist das mit Abstand ineffizienteste Sortierverfahren, dass es gibt. Versuchs mal mit Quick Sort, das ist bei mehr als 10 zu sortierenden Elementen das mit Abstand schnellste Verfahren.