Insertionsort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{subst:Selectionsort}}“) |
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
{{ | [[Selectionsort]] ist ein [[Algorithmus|Sortieralgorithmus]] und arbeitet wie folgt: | ||
Gegeben: Eine Liste <code>A</code> der Länge <code>n</code>: | |||
* 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 <code>n</code> Mal: | |||
** 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 <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}} | |||
Version vom 16. Januar 2024, 17:36 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
