Bubblesort mit (Pseudo)code erklären !

[fizzle]

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 :

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]

Wenn du sagst du hast das Prinzip verstanden ist der Code doch fast selbsterklärend.
Hast du eine konkrete Frage dazu?

 

[petap]

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]

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]

:= 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]

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]

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]

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]

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]

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]

Wenn es maximal n Durchläufe gibt wäre doch die quatratische Laufzeit nicht gegeben oder ?

 

[ablabs]

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]

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]

Danke