Bubblesort mit (Pseudo)code erklären !

fizzle

Captain
Dabei seit
Nov. 2008
Beiträge
3.920
Hallo,

die Funktionsweise des BS an sich habe ich verstanden, das Prinzip des wiederholten Durchschlaufs eines Arrays und die Vertauschung der benachbarten Elemente ist überschaubar.

Mein Problem ist es dieses Verfahren an einen Programmcode oder Pseudocode zu erklären. Es ist Bestandteil meiner Abiturpräsentation und deshalb muss ich es einigermaßen durchdrungen haben :)

Hier ein Pseudocode von Wiki :

Code:
prozedur bubbleSort( A : Liste sortierbarer Elemente ) 
  n := Länge( A )
  wiederhole
    vertauscht := falsch
    für jedes i von 1 bis n - 1 wiederhole 
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      ende falls
    ende für
    n := n - 1
  solange vertauscht und n >= 1
prozedur ende
Könnte jemand den Code näher erläutern ?
 

ablabs

Cadet 2nd Year
Dabei seit
Nov. 2007
Beiträge
27
Wenn du sagst du hast das Prinzip verstanden ist der Code doch fast selbsterklärend.
Hast du eine konkrete Frage dazu?
 

petap

Ensign
Dabei seit
Juli 2008
Beiträge
245
Wenn du das Prinzip verstanden hast, dann sollte es dir doch auch möglich sein den Pseudocode in soweit zu durchdringen, dass du konkrete Fragen dazu stellen kannst.

Edit: 2 Dumme...^^
 

fizzle

Captain
Ersteller dieses Themas
Dabei seit
Nov. 2008
Beiträge
3.920
Ja dann werd ich mal konkreter..

Also z.B. n := Länge (A) heißt das, dass n gleich die länge des Arrays ist ohne ungleich ? Die gleiche Frage gilt für vertausche := wahr ..
 

ablabs

Cadet 2nd Year
Dabei seit
Nov. 2007
Beiträge
27
:= ist eine Zuweisung.
n := Länge( A ) bedeutet dann also dass danach in n die Länge des Arrays steht.

vertauscht wird am Anfang der Schleife auf "falsch" gesetzt und wenn etwas vertauscht wird auf wahr (vertauscht := wahr)

Klar soweit?
 

Tux1000

Cadet 4th Year
Dabei seit
Dez. 2005
Beiträge
83
n := Länge (A)
ist doch nur eine Zuweisung.
n ist also die Anzahl der Elemente in A. In Java würde das z.B. so aussehen:
int n = A.size();

edit:
Zu langsam
 

fizzle

Captain
Ersteller dieses Themas
Dabei seit
Nov. 2008
Beiträge
3.920
Okay gut dann wird ja am Anfang das n sozusagen festgesetzt !

Dann wird vertauschen auf false gesetzt das heißt es wird erstmal nichts vertauscht ..

Im nächsten Schritt hat er eine Laufvariable(?) i, die einmal das ganze Array durchläuft, dabei werden zwei benachbarte Elemente vertauscht falls die erstere größer ist

dann wird erst vertausche auf wahr gesetzt (warum erst jetzt ?)

ende für n := 1 -n -> was meint er damit ? Dem Einmaligen Durchschlauf eines Arrays ?

solange vertauscht und n >= 1 -> verstehe ich auch nicht so ganz ?!
 

petap

Ensign
Dabei seit
Juli 2008
Beiträge
245
Ich habe das Gefühl, du hast das Prinzip überhaupt nicht verstanden.

Du hast eine Liste von Elementen: A = { 9,1,5,4,8,7,5,2,4,7}

Der Algorithmus macht jetzt folgendes:
1. i=1
2. vergleiche A mit A[i+1], also 9 und 1.
3. ist 9 A größer als A[i+1] (so wie hier, weil 9>1), dann werden die Elemente getauscht und die Flag "vertauscht" auf true gesetzt. Jetzt ist die Liste A = { 1,9,5,4,8,7,5,2,4,7}
4. jetzt wird i erhöht und zu Schritt 2 gegangen. Da wird dann 9 (A[2]) und 5 (A[2+1]) verglichen.
5. Das wird so lange gemacht, bis die Liste einmal durchlaufen wurde. Damit bist du *sicher*, dass die größte Zahl am Ende steht. Das ist der "für"-Block im Pseudocode
6. Der "wiederhole"-Block wird n mal ausgeführt. Vor dem 2. Durchlauf sieht deine Liste so aus: A = {1,5,4,8,7,5,2,4,7,9}. Da weißt du ja schon, dass die größte Zahl am Ende steht. Ein Vergleich von A[n-1] und A[n] (in diesem Fall 8 und 9, da die 8 ja im Laufe des 2. Durchlaufs nach hinten geschoben wird) ist also nicht nötig. Deswegen wird n um 1 verringert. Du sparst dir also pro Interation einen Vergleich.
7. Der Algorithmus terminiert wenn die letzten n-1 Elemente richtig sind (dann ist n=1) oder wenn es keinen Tausch gab. Dann sind die Elemente zufällig schon in der richtigen Reihenfolge.

Nimm mal eine Liste von Zahlen und ein Blatt Papier. Dann wendest du den Algorithmus ganz stumpf auf diese Zahlen an. Dabei wirst du dann verstehen, was genau passiert.
 

fizzle

Captain
Ersteller dieses Themas
Dabei seit
Nov. 2008
Beiträge
3.920
Danke zunächst für die ausführliche Erklärung.

n:= n-1 steht also für die Verringerung von i je durchlauf ?

solange vertauscht und n >= 1 -> das heißt also er wiederholt es solange, bis vertauscht auf war ist (also vertauschungen durchgeführt werden) und n großer 1 ist ( wenn n=1 ist, sind alle Elemente sortier)



Richtig ?
 

petap

Ensign
Dabei seit
Juli 2008
Beiträge
245
ne. das heißt nicht "wiederhole solange BIS ..." sondern "wiederhole solange ... gegeben ist". Es wird also so lange ausgeführt, bis vertauscht falsch ist ODER n<1 ist.

n ist ja am Anfang die Länge von A und wird in jedem Schritt um 1 verkleinert. Es gibt von der wiederhole-Schleife also maximal n Durchläufe.
 

fizzle

Captain
Ersteller dieses Themas
Dabei seit
Nov. 2008
Beiträge
3.920
Wenn es maximal n Durchläufe gibt wäre doch die quatratische Laufzeit nicht gegeben oder ?
 

ablabs

Cadet 2nd Year
Dabei seit
Nov. 2007
Beiträge
27
Bei n Durchläufen hättest du lineare Laufzeit - ja.
Aber hier sind es nicht n durchläufe sondern n * n -> quadratische Laufzeit.
Schau mal genau hin, in der äußeren Schleife hast du noch ein
"für jedes i von 1 bis n - 1 wiederhole" was auch wieder eine Schleife von 1 bis n ist
Damit hast du eine Schleife in der Schleife -> n*n -> O(n²)
 

petap

Ensign
Dabei seit
Juli 2008
Beiträge
245
Genau so ist es. Ich habe ja geschrieben: "Es gibt von der wiederhole-Schleife also maximal n Durchläufe." *Zusätzlich* ist *in* der wiederhole-Schleife noch die für-Schleife, die n/2 mal läuft. Du hast also eine Laufzeit von n*n/2.
 

fizzle

Captain
Ersteller dieses Themas
Dabei seit
Nov. 2008
Beiträge
3.920
Danke ;)
 
Top