Bubble-sort: Unterschied zwischen den Versionen

Zeile 1:

== Einführung ==

Der Bubble Sort ist ein relativ einfacher [[Sortieren|Sortieralgorithmus]]. In der Bubble-Phase wird die ~~Eingabe-Liste~~ von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie ~~getauscht~~. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Der Bubble Sort ist ein relativ einfacher [[Sortieren|Sortieralgorithmus]]. In der Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie vertauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird ~~solange~~ wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. ~~Auch~~ werden ~~immer~~ zwei Zahlen miteinander in „Bubbles“ vertauscht.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt an das Ende der Liste. Es werden jeweils zwei Zahlen miteinander in „Bubbles“ vertauscht.

== Beispiel ==

[[Datei:Animation Bubble Sort.gif|mini]]

Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte ~~und vorletzte~~ Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich ~~letzte/vorletzte/vorvorletzte...~~.

Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich der letzten drei Positionen mehr.

'''''55 07''''' 78 12 42 1. Durchlauf

Zeile 28:

07 '''''12 42''''' 55 78 Letzter Vergleich

'''''07 12''''' 42 55 78 4. Durchlauf + ~~Letzter~~ Vergleich

'''''07 12''''' 42 55 78 4. Durchlauf + letzter Vergleich

07 12 42 55 78 Fertig sortiert.

== ~~Pseudo Code~~ ==

== Pseudocode ==

Der [[Algorithmus]] sieht im Pseudocode so aus:

prozedur bubbleSort(A ist Liste sortierbarer Elemente)

n = Länge von A

wiederhole solange n>1

wiederhole solange n > 1

n=n-1

n = n - 1

i=0

i = 0

wiederhole solange i<n-1

wiederhole solange i < n

~~i=i+1~~

falls A[i] > A[i + 1] dann

falls A ~~an der Stelle~~ i > A ~~an der Stelle~~ i+1 dann

tausche A[i] und A[i + 1]

A ~~tausche~~ i und i+1

ende falls

i = i + 1

ende wiederhole

ende prozedur

</syntaxhighlight>

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

[[Kategorie:FI_I_TP2]]

@@ Zeile 1: / Zeile 1: @@
 == Einführung ==
-Der Bubble Sort ist ein relativ einfacher [[Sortieren|Sortieralgorithmus]]. In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.
+Der Bubble Sort ist ein relativ einfacher [[Sortieren|Sortieralgorithmus]]. In der Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie vertauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.
-Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.
+Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.
-Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Auch werden immer zwei Zahlen miteinander in „Bubbles“ vertauscht.
+Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt an das Ende der Liste. Es werden jeweils zwei Zahlen miteinander in „Bubbles“ vertauscht.
 == Beispiel ==
 [[Datei:Animation Bubble Sort.gif|mini]]
-Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte und vorletzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich letzte/vorletzte/vorvorletzte....
+Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich der letzten drei Positionen mehr.
 '''''55 07''''' 78 12 42   1. Durchlauf
@@ Zeile 28: / Zeile 28: @@
 '''''12 42''''' 55 78   Letzter Vergleich
-'''''07 12''''' 42 55 78   4. Durchlauf + Letzter Vergleich
+'''''07 12''''' 42 55 78   4. Durchlauf + letzter Vergleich
 12 42 55 78   Fertig sortiert.
-== Pseudo Code ==
+== Pseudocode ==
 Der [[Algorithmus]] sieht im Pseudocode so aus:
-<syntaxhighlight>
+<syntaxhighlight lang="text">
 prozedur bubbleSort(A ist Liste sortierbarer Elemente)
- n = Länge von A
+    n = Länge von A
- wiederhole solange n>1
+    wiederhole solange n > 1
- n=n-1
+        n = n - 1
- i=0
+        i = 0
-  wiederhole solange i<n-1
+        wiederhole solange i < n
-    i=i+1
+            falls A[i] > A[i + 1] dann
-    falls A an der Stelle i > A an der Stelle i+1 dann
+                tausche A[i] und A[i + 1]
-          A tausche i und i+1
+            ende falls
-    ende falls
+            i = i + 1
-  ende wiederhole
+        ende wiederhole
- ende wiederhole
+    ende wiederhole
 ende prozedur
 </syntaxhighlight>
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]
 [[Kategorie:FI_I_TP2]]