Bubblesort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) K (math statt code) |
Ntr (Diskussion | Beiträge) K (da hat ein leerzeichen gefehlt ;-;) |
||
| Zeile 11: | Zeile 11: | ||
== Laufzeit == | == Laufzeit == | ||
Eine Liste mit <math>n</math> Elementen muss <math>n-1</math> Mal durchgegangen werden und bei jedem Durchgang werden <math>n-1</math> Vergleiche angestellt. Insgesamt sind das <math>(n-1)^2</math> Vergleiche. Damit bewegt sich die [[Laufzeit]] in{{O|n^2}}. | Eine Liste mit <math>n</math> Elementen muss <math>n-1</math> Mal durchgegangen werden und bei jedem Durchgang werden <math>n-1</math> Vergleiche angestellt. Insgesamt sind das <math>(n-1)^2</math> Vergleiche. Damit bewegt sich die [[Laufzeit]] in {{O|n^2}}. | ||
{{Footer Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=Iv3vgjM8Pv4 Bubblesort getanzt {{Flagge|GB}}]}} | {{Footer Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=Iv3vgjM8Pv4 Bubblesort getanzt {{Flagge|GB}}]}} | ||
Version vom 15. März 2024, 16:30 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 Elementen muss Mal durchgegangen werden und bei jedem Durchgang werden Vergleiche angestellt. Insgesamt sind das Vergleiche. Damit bewegt sich die Laufzeit in .
