Bubblesort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) K (→Laufzeit) |
Sn (Diskussion | Beiträge) K (Kategorie) Markierungen: Zurückgesetzt Visuelle Bearbeitung |
||
| Zeile 13: | Zeile 13: | ||
Eine Liste mit <code>n</code> Elementen muss <code>n-1</code> Mal durchgegangen werden und bei jedem Durchgang werden <code>n-1</code> Vergleiche angestellt. Insgesamt sind das <code>(n-1)²</code> Vergleiche. Damit bewegt sich die [[Laufzeit]] in <math>\mathcal{O}(n^2)</math>. | Eine Liste mit <code>n</code> Elementen muss <code>n-1</code> Mal durchgegangen werden und bei jedem Durchgang werden <code>n-1</code> Vergleiche angestellt. Insgesamt sind das <code>(n-1)²</code> Vergleiche. Damit bewegt sich die [[Laufzeit]] in <math>\mathcal{O}(n^2)</math>. | ||
{{Navigationsleiste Sortieralgorithmen}} | {{Navigationsleiste Sortieralgorithmen}} | ||
[[Kategorie:Sortieralgorithmen]] | |||
Version vom 14. März 2024, 18:00 Uhr
Bubblesort ist ein Sortieralgorithmus und arbeitet wie folgt:
Gegeben: Liste A der Länge n.
- Falls
n < 2:Aist sortiert, brich ab. Ansonsten… - Wiederhole
n-1Mal:- Gehe von
A[0]bisA[n-2]durch - Betrachte jeweils ein Element und seinen rechten Nachbarn (also
A[i]undA[i+1]) - Wenn
A[i] > A[i+1], vertausche die beiden
- Gehe von
- Danach ist die Liste sortiert, gib die sortierte Liste als Ergebnis zurück
Laufzeit
Eine Liste mit n Elementen muss n-1 Mal durchgegangen werden und bei jedem Durchgang werden n-1 Vergleiche angestellt. Insgesamt sind das (n-1)² Vergleiche. Damit bewegt sich die Laufzeit in .
Weblinks
