Selectionsort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) (Seite angelegt) |
Sn (Diskussion | Beiträge) |
||
| Zeile 10: | Zeile 10: | ||
== Laufzeit == | == Laufzeit == | ||
Die Liste mit <code>n</code> Elementen muss <code>n</code> Mal durchlaufen werden, wobei beim ersten Durchgang <code>n</code> Elemente betrachtet werden, beim zweiten Durchgang <code>n-1</code> Elemente, beim dritten Durchgang <code>n-2</code> 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 <math>\mathcal{O}(n^2)</math>. | Die Liste mit <code>n</code> Elementen muss <code>n</code> Mal durchlaufen werden, wobei beim ersten Durchgang <code>n</code> Elemente betrachtet werden, beim zweiten Durchgang <code>n-1</code> Elemente, beim dritten Durchgang <code>n-2</code> 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 <math>\mathcal{O}(n^2)</math>. | ||
{{Navigationsleiste Sortieralgorithmen}} | {{Navigationsleiste Sortieralgorithmen}} | ||
Version vom 13. März 2024, 15:33 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 n Elementen muss n Mal durchlaufen werden, wobei beim ersten Durchgang n Elemente betrachtet werden, beim zweiten Durchgang n-1 Elemente, beim dritten Durchgang n-2 Elemente und so weiter, bis beim letzten Durchgang nur noch ein Element betrachtet wird. Insgesamt werden also Elemente betrachtet. Damit liegt die Laufzeit in .
Weblinks
