Bubblesort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Sn (Diskussion | Beiträge) K (Vorlage O) |
||
| Zeile 11: | Zeile 11: | ||
== Laufzeit == | == Laufzeit == | ||
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 | 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{{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, 10:07 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.
