Bubblesort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) K (→Laufzeit) |
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| (7 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 7: | Zeile 7: | ||
** Gehe von <code>A[0]</code> bis <code>A[n-2]</code> durch | ** Gehe von <code>A[0]</code> bis <code>A[n-2]</code> durch | ||
** Betrachte jeweils ein Element und seinen rechten Nachbarn (also <code>A[i]</code> und <code>A[i+1]</code>) | ** Betrachte jeweils ein Element und seinen rechten Nachbarn (also <code>A[i]</code> und <code>A[i+1]</code>) | ||
** | ** Falls <code>A[i] > A[i+1]</code>, vertausche die beiden | ||
* Danach ist die Liste sortiert, gib die sortierte Liste als Ergebnis zurück | * Danach ist die Liste sortiert, gib die sortierte Liste als Ergebnis zurück | ||
== Laufzeit == | == Laufzeit == | ||
Eine Liste mit < | 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}}. | ||
{{ | |||
== Implementierung in Python == | |||
<syntaxhighlight lang="python" line> | |||
def swap(A,i,j): | |||
temp = A[i] | |||
A[i] = A[j] | |||
A[j] = temp | |||
def bubblesort(A): | |||
for n in range(len(A)): | |||
for i in range(len(A)-1): | |||
if A[i] > A[i+1]: | |||
swap(A,i,i+1) | |||
return A | |||
</syntaxhighlight> | |||
{{Footer Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=Iv3vgjM8Pv4 Bubblesort getanzt {{Flagge|GB}}]}} | |||
Aktuelle Version vom 22. Mai 2024, 09:39 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]) - Falls
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 .
Implementierung in Python
def swap(A,i,j):
temp = A[i]
A[i] = A[j]
A[j] = temp
def bubblesort(A):
for n in range(len(A)):
for i in range(len(A)-1):
if A[i] > A[i+1]:
swap(A,i,i+1)
return A
