Bubblesort - Versionsgeschichte

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Bubble-sort nach Bubblesort

2026-04-28T08:51:48Z

Flbkwikiadmin verschob die Seite Bubble-sort nach Bubblesort

← Nächstältere Version		Version vom 28. April 2026, 10:51 Uhr
(kein Unterschied)

Flbkwikiadmin am 28. April 2026 um 08:50 Uhr

2026-04-28T08:50:55Z

← Nächstältere Version		Version vom 28. April 2026, 10:50 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	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.		Der Bubble Sort (Sortieren durch Aufsteigen) ist ein verhältnismäßig einfacher [[Sortieren\|Sortieralgorithmus]]. In der sogenannten Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuell betrachtete Element mit seinem rechten Nachbarn verglichen. Falls die beiden Elemente das vorgegebene Sortierkriterium verletzen (z. B. das linke größer als das rechte ist), werden sie vertauscht. Am Ende einer solchen Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe fest am Ende der Liste.

	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.		Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das jeweils letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es bereits seine finale Position erreicht hat und 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. Es werden ~~jeweils~~ zwei Zahlen miteinander in „Bubbles“ vertauscht.		Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Luftblasen im Wasser (daher der Name ''Bubble'') Schritt für Schritt immer weiter nach oben an das Ende der Liste. Es werden stets zwei benachbarte Zahlen miteinander in „Bubbles“ verglichen und bei Bedarf vertauscht.

	== Beispiel ==		== Beispiel ==
	[[Datei:Animation Bubble Sort.gif\|mini]]		[[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 Position nicht mehr ~~zu vergleichen~~. ~~→ Dritter~~ Durchlauf~~: kein Vergleich der~~ letzten ~~drei~~ Positionen ~~mehr~~.		Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett und kursiv markierten Zahlen werden jeweils miteinander verglichen. Ist die linke Zahl größer als die rechte, so werden beide vertauscht. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts an die letzte Position. Im zweiten Durchlauf muss diese letzte Position folglich nicht mehr verglichen werden. Im dritten Durchlauf entfallen die letzten zwei Positionen, und so weiter.

	'''''55 07''''' 78 12 42 ~~1. Durchlauf~~		'''1. Durchlauf'''
			* '''''55 07''''' 78 12 42 (55 ist größer als 07 -> Tausch)
			* 07 '''''55 78''''' 12 42 (55 ist nicht größer als 78 -> kein Tausch)
			* 07 55 '''''78 12''''' 42 (78 ist größer als 12 -> Tausch)
			* 07 55 12 '''''78 42''''' (78 ist größer als 42 -> Tausch, letzter Vergleich)

	07 '''''55 78''''' 12 42		'''2. Durchlauf''' (78 ist bereits fest positioniert)
			* '''''07 55''''' 12 42 78
			* 07 '''''55 12''''' 42 78 (Tausch)
			* 07 12 '''''55 42''''' 78 (Tausch, letzter Vergleich)

	07 55 '''''78 12''''' 42		'''3. Durchlauf''' (55 und 78 sind fest positioniert)
			* '''''07 12''''' 42 55 78
			* 07 '''''12 42''''' 55 78 (Letzter Vergleich)

	~~07 55 12~~ '''''~~78 42~~''''' Letzter Vergleich		'''4. Durchlauf'''
			* '''''07 12''''' 42 55 78 (Letzter Vergleich)

	~~'''''07 55''''' 12 42 78 2. Durchlauf~~		07 12 42 55 78 – Die Liste ist fertig sortiert.

	~~07 '''''55 12''''' 42 78~~

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

	~~'''''07 12''''' 42 55 78 3. Durchlauf~~

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

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

	07 12 42 55 78 ~~Fertig~~ sortiert.

	== Pseudocode ==		== Pseudocode ==
	Der [[Algorithmus]] sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode der unoptimierten Basisvariante so aus:

	<syntaxhighlight lang="text">		<syntaxhighlight lang="text">
Zeile 50:		Zeile 48:
	ende prozedur		ende prozedur
	</syntaxhighlight>		</syntaxhighlight>

			== Komplexität ==
			Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Bubble Sort für ein [[Array]] der Länge <math>n</math>.

			=== Best Case ===
			Das Best-Case-Szenario tritt ein, wenn die Liste bereits von Beginn an vollständig aufsteigend sortiert ist.
			* '''Unoptimierte Variante (siehe Pseudocode):''' Auch wenn keine Vertauschungen notwendig sind, durchläuft der oben notierte Algorithmus die Liste strikt weiter. Er führt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. Die Zeitkomplexität liegt hier also bei <math>O(n^2)</math>.
			* '''Optimierte Variante (Praxis-Standard):''' In der Praxis wird Bubble Sort fast immer mit einer Abbruchbedingung (z. B. einem Boolean-Flag `wurdeGetauscht`) implementiert. Findet in einem kompletten Durchlauf kein einziger Tausch statt, weiß der Algorithmus, dass die Liste sortiert ist, und bricht vorzeitig ab. In dieser optimierten Form benötigt er im Best Case nur <math>n - 1</math> Vergleiche. Die Zeitkomplexität sinkt dadurch auf eine lineare Laufzeit von <math>O(n)</math>.

			=== Average Case ===
			Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
			Etwa die Hälfte der maximal möglichen Vertauschungen muss durchgeführt werden. Sowohl die Anzahl der Vergleiche als auch die der Vertauschungen wachsen quadratisch zur Eingabemenge <math>n</math>. Konstante Faktoren (wie die Halbierung der Tauschoperationen) werden in der Landau-Notation ignoriert. Die Zeitkomplexität im Average Case liegt somit bei <math>O(n^2)</math>.

			=== Worst Case ===
			Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
			In diesem Fall ist das aktuell betrachtete Element immer größer als sein rechter Nachbar. Der Algorithmus muss in jedem einzelnen Schritt eine Vertauschung durchführen, da jedes Element an das andere Ende der Liste "blubbern" muss. Er führt die maximale Anzahl an Vergleichen und Vertauschungen durch: <math>\frac{n(n - 1)}{2}</math>. Da der Term mit der höchsten Potenz das Wachstum dominiert, liegt die Komplexitätsklasse des Bubble Sorts im Worst Case bei <math>O(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Flbkwikiadmin am 2. März 2026 um 11:27 Uhr

2026-03-02T11:27:51Z

← Nächstältere Version		Version vom 2. März 2026, 13:27 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== 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 ==		== Beispiel ==
	[[Datei:Animation Bubble Sort.gif\|mini]]		[[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		'''''55 07''''' 78 12 42 1. Durchlauf
Zeile 28:		Zeile 28:
	07 '''''12 42''''' 55 78 Letzter Vergleich		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.		07 12 42 55 78 Fertig sortiert.

	== ~~Pseudo Code~~ ==		== Pseudocode ==
	Der [[Algorithmus]] sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode so aus:
	<syntaxhighlight>
			<syntaxhighlight lang="text">
	prozedur bubbleSort(A ist Liste sortierbarer Elemente)		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		ende prozedur
	</syntaxhighlight>		</syntaxhighlight>

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Thomas: /* Pseudo Code */

2026-02-20T10:58:34Z

Pseudo Code

← Nächstältere Version		Version vom 20. Februar 2026, 12:58 Uhr
Zeile 49:		Zeile 49:
	ende prozedur		ende prozedur
	</syntaxhighlight>		</syntaxhighlight>
			[[Kategorie:Programmierung]]
			[[Kategorie:AHR_I_Informatik_LK]]
			[[Kategorie:FI_I_TP2]]

Thomas: /* Einführung */

2026-02-18T13:20:53Z

Einführung

← Nächstältere Version		Version vom 18. Februar 2026, 15:20 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Der Bubble Sort ist ein relativ einfacher 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 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.

	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 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.

Thomas: /* Pseudo Code */

2026-02-18T13:20:28Z

Pseudo Code

← Nächstältere Version		Version vom 18. Februar 2026, 15:20 Uhr
Zeile 33:		Zeile 33:

	== Pseudo Code ==		== Pseudo Code ==
	Der Algorithmus sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode so aus:
	<syntaxhighlight>		<syntaxhighlight>
	prozedur bubbleSort(A ist Liste sortierbarer Elemente)		prozedur bubbleSort(A ist Liste sortierbarer Elemente)

Thomas: /* Pseudo Code */

2026-02-18T13:20:16Z

Pseudo Code

← Nächstältere Version		Version vom 18. Februar 2026, 15:20 Uhr
Zeile 34:		Zeile 34:
	== Pseudo Code ==		== Pseudo Code ==
	Der Algorithmus sieht im Pseudocode so aus:		Der Algorithmus sieht im Pseudocode so aus:
	<syntaxhighlight ~~lang="java"~~>		<syntaxhighlight>
	prozedur bubbleSort(A ist Liste sortierbarer Elemente)		prozedur bubbleSort(A ist Liste sortierbarer Elemente)
			n = Länge von A
	n = Länge von A		wiederhole solange n>1
			n=n-1
	wiederhole solange n>1		i=0
			wiederhole solange i<n-1
	n=n-1

	i=0

	wiederhole solange i<n-1

	i=i+1		i=i+1

	falls A an der Stelle i > A an der Stelle i+1 dann		falls A an der Stelle i > A an der Stelle i+1 dann
			A tausche i und i+1
	A tausche i und i+1		ende falls
			ende wiederhole
	ende falls		ende wiederhole

	ende wiederhole

	ende wiederhole

	ende prozedur		ende prozedur
	</		</syntaxhighlight>
	syntaxhighlight>

Thomas: Die Seite wurde neu angelegt: „== Einführung == Der Bubble Sort ist ein relativ einfacher 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. Die Bu…“

2026-02-18T13:18:18Z

Die Seite wurde neu angelegt: „== Einführung == Der Bubble Sort ist ein relativ einfacher 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. Die Bu…“

Neue Seite

== Einführung ==
Der Bubble Sort ist ein relativ einfacher 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.

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.

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.

== 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....

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

07 '''''55 78''''' 12 42

07 55 '''''78 12''''' 42

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

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

07 '''''55 12''''' 42 78

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

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

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

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

07 12 42 55 78 Fertig sortiert.

== Pseudo Code ==
Der Algorithmus sieht im Pseudocode so aus:
<syntaxhighlight lang="java">
prozedur bubbleSort(A ist Liste sortierbarer Elemente)

n = Länge von A

wiederhole solange n>1

n=n-1

i=0

wiederhole solange i<n-1

i=i+1

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

A tausche i und i+1

ende falls

ende wiederhole

ende wiederhole

ende prozedur
</
syntaxhighlight>