Bubblesort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) Seite angelegt |
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| 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}} | ||
Version vom 13. Januar 2024, 13:55 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
