Bubblesort: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
durchsicht>Wiki-Durchsicht Durchsicht vom 15.11.2026: Befunde behoben |
||
| Zeile 1: | Zeile 1: | ||
== Einführung == | == Einführung == | ||
{{#ev:youtube|ZDIicT_EWnc|320|poster=Datei:Vorschau YouTube ZDIicT_EWnc.jpg|title=Bubblesort Schritt für Schritt – mit Java-Code}} | |||
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. | 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. | ||
| Zeile 59: | Zeile 57: | ||
Das Best-Case-Szenario tritt ein, wenn die Liste bereits von Beginn an vollständig aufsteigend sortiert ist. | 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>. | * '''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 | * '''Optimierte Variante (Praxis-Standard):''' In der Praxis wird Bubble Sort fast immer mit einer Abbruchbedingung (z. B. einem Boolean-Flag <code>wurdeGetauscht</code>) 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 === | === Average Case === | ||
| Zeile 67: | Zeile 65: | ||
=== Worst Case === | === Worst Case === | ||
Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist. | 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 | 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 bei jedem Vergleich der linke Nachbar größer ist. 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]] | ||