Insertionsort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) K (→Laufzeit) |
Sn (Diskussion | Beiträge) K (Das ist ja peinlich... m() |
||
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
[[ | [[Insertionsort]] ist ein [[Algorithmus|Sortieralgorithmus]] und arbeitet wie folgt: | ||
Gegeben: Eine Liste <code>A</code> der Länge <code>n</code>: | Gegeben: Eine Liste <code>A</code> der Länge <code>n</code>: | ||
| Zeile 13: | Zeile 13: | ||
Die gesamte Liste wird einmal durchlaufen, wobei für jedes betrachtete Element im schlechtesten Fall der gesamte unsortierte Bereich durchlaufen werden muss. Beim ersten Element hat dieser unsortierte Bereich die Größe <code>0</code>, beim zweiten Element die Größe <code>1</code>, beim dritten Element die Größe <code>3</code> und so weiter, bis der sortierte Bereich am Ende <code>n-1</code> Elemente enthält. | Die gesamte Liste wird einmal durchlaufen, wobei für jedes betrachtete Element im schlechtesten Fall der gesamte unsortierte Bereich durchlaufen werden muss. Beim ersten Element hat dieser unsortierte Bereich die Größe <code>0</code>, beim zweiten Element die Größe <code>1</code>, beim dritten Element die Größe <code>3</code> und so weiter, bis der sortierte Bereich am Ende <code>n-1</code> Elemente enthält. | ||
Insgesamt werden also <math>1+2+3+\cdots + (n-1) = \frac{n^2-n}{2}</math> Elemente betrachtet, die [[Laufzeit]] liegt also insgesamt in | Insgesamt werden also <math>1+2+3+\cdots + (n-1) = \frac{n^2-n}{2}</math> Elemente betrachtet, die [[Laufzeit]] liegt also insgesamt in {{O|n^2}}. | ||
{{ | {{Footer Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=EdIKIf9mHk0 Insertionsort getanzt {{Flagge|GB}}]}} | ||
Aktuelle Version vom 22. Mai 2024, 08:46 Uhr
Insertionsort 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
- Gehe durch die ganze Liste durch:
- Betrachte das erste Element des unsortierten Bereichs.
- Gehe durch den ganzen sortierten Bereich
- Finde die Position, an der dieses Element in den sortierten Bereich gehört, und sortiere es dort ein.
Laufzeit
Die gesamte Liste wird einmal durchlaufen, wobei für jedes betrachtete Element im schlechtesten Fall der gesamte unsortierte Bereich durchlaufen werden muss. Beim ersten Element hat dieser unsortierte Bereich die Größe 0, beim zweiten Element die Größe 1, beim dritten Element die Größe 3 und so weiter, bis der sortierte Bereich am Ende n-1 Elemente enthält.
Insgesamt werden also Elemente betrachtet, die Laufzeit liegt also insgesamt in .
