Selectionsort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) Seite angelegt |
Sn (Diskussion | Beiträge) K Vorlage O |
||
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| Zeile 10: | Zeile 10: | ||
== Laufzeit == | == Laufzeit == | ||
Die Liste mit < | Die Liste mit <math>n</math> Elementen muss <math>n</math> Mal durchlaufen werden, wobei beim ersten Durchgang <math>n</math> Elemente betrachtet werden, beim zweiten Durchgang <math>n-1</math> Elemente, beim dritten Durchgang <math>n-2</math> Elemente und so weiter, bis beim letzten Durchgang nur noch ein Element betrachtet wird. Insgesamt werden also <math>1+2+3+\cdots+n = \frac{n^2 + n}{2}</math> Elemente betrachtet. Damit liegt die [[Laufzeit]] in {{O|n^2}}. | ||
{{ | {{Footer Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=0-W8OEwLebQ Selectionsort getanzt {{Flagge|GB}}]}} | ||
Aktuelle Version vom 15. März 2024, 10:03 Uhr
Selectionsort ist ein Sortieralgorithmus und arbeitet wie folgt:
Gegeben: Eine Liste A der Länge n:
- Unterteile die Liste in einen sortierten und einen unsortierten Bereich.
- Der sortierte Bereich ist zu Beginn leer, der unsortierte Bereich enthält die ganze Liste
- Wiederhole
nMal:- Gehe durch den gesamten unsortierten Bereich durch und finde das kleinste Element
- Füge dieses Element am Ende des sortierten Bereichs ein
Laufzeit
Die Liste mit Elementen muss Mal durchlaufen werden, wobei beim ersten Durchgang Elemente betrachtet werden, beim zweiten Durchgang Elemente, beim dritten Durchgang Elemente und so weiter, bis beim letzten Durchgang nur noch ein Element betrachtet wird. Insgesamt werden also Elemente betrachtet. Damit liegt die Laufzeit in .
